首页 > 其他分享 >萌新的多项式学习笔记(板子)

萌新的多项式学习笔记(板子)

时间:2024-02-02 10:33:40浏览次数:34  
标签:const int 多项式 板子 萌新 double return cp

萌新的多项式学习笔记(板子)

详细讲解

FFT

直接放板子

struct cp{
	double x,y;
	cp(double xx=0,double yy=0){x=xx,y=yy;}
};
int r[maxn];
cp operator + (const cp &a,const cp &b){return cp(a.x+b.x,a.y+b.y);}
cp operator - (const cp &a,const cp &b){return cp(a.x-b.x,a.y-b.y);}
cp operator * (const cp &a,const cp &b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
cp operator * (const cp &a,double b){return cp(a.x*b,a.y*b);}
const double Pi=acos(-1.0);
void fft(cp *a,int N,int op){
	for(int i=0;i<N;i++)if(i<r[i])swap(a[i],a[r[i]]);
	for(int i=1;i<N;i<<=1){
		cp wn=cp(cos(Pi/i),op*sin(Pi/i));
		for(int j=0;j<N;j+=i<<1){
			cp w=cp(1,0);
			for(int k=0;k<i;k++,w=w*wn){
				cp x=a[j+k],y=w*a[j+k+i];
				a[j+k]=x+y;a[j+k+i]=x-y;
			}
		}
	}
}
#define lbt(x) ((x)&-(x))
void work(cp *a,cp *b,cp *c,int M){
	int N=M;
	while(N>lbt(N))N+=lbt(N);
	int l=__lg(N);
	for(int i=0;i<N;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));

	fft(a,N,1);
	fft(b,N,1);
	for(int i=0;i<N;i++)c[i]=a[i]*b[i];
	fft(c,N,-1);
	for(int i=0;i<N;i++)c[i].x=(int)(c[i].x/N+0.5);
}

NTT

\(10^9+7\) 不是 NTT 模数。

其余所有模数大多都可以取 \(3189\) 作为原根。

直接放板子

int ksm(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
	return ans;
}
#define lbt(x) ((x)&-(x))
const int g=3189;
void ntt(int *a,int N,int op){
	for(int i=0;i<N;i++)if(i<r[i])swap(a[i],a[r[i]]);
	for(int i=1;i<N;i<<=1){
		int wn=ksm(g,(mod-1)/(i<<1));
		if(op==-1)wn=ksm(wn,mod-2);
		for(int j=0;j<N;j+=(i<<1)){
			int w=1,x,y;
			for(int k=j;k<j+i;k++,w=w*wn%mod){
				x=a[k],y=w*a[k+i]%mod;
				a[k]=(x+y)%mod;
				a[k+i]=(x-y+mod)%mod;
			}
		}
	}
}
void work(int *a,int *b,int *c,int M){
	int N=M;
	while(N!=lbt(N))N+=lbt(N);
	int l=__lg(N);
	for(int i=0;i<N;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));

	memset(c,0,sizeof(int)*N);

	ntt(a,N,1);
	ntt(b,N,1);
	for(int i=0;i<=N;i++)c[i]=a[i]*b[i]%mod;
	ntt(c,N,-1);
	int inv=ksm(N,mod-2);
	for(int i=0;i<=M;i++)c[i]=c[i]*inv%mod;

	memset(a,0,sizeof(int)*N);
	memset(b,0,sizeof(int)*N);
}

标签:const,int,多项式,板子,萌新,double,return,cp
From: https://www.cnblogs.com/Augury/p/18002471

相关文章

  • 【Loading】ctfshow_WriteUp | _萌新
    萌新_密码1题目密文:53316C6B5A6A42684D3256695A44566A4E47526A4D5459774C5556375A6D49324D32566C4D4449354F4749345A6A526B4F48303D提交格式:KEY{XXXXXXXXXXXXXX}分析所有字符由数字和ABCDEF组成,先用HEX解码得到S1lkZjBhM2ViZDVjNGRjMTYwLUV7ZmI2M2VlMDI5OGI4ZjRkOH0=。......
  • R语言非线性方程数值分析生物降解、植物生长数据:多项式、渐近回归、负指数方程、幂函
    全文链接:https://tecdat.cn/?p=33742原文出处:拓端数据部落公众号简介在选择最佳拟合实验数据的方程时,可能需要一些经验。当我们没有文献信息时该怎么办?我们建立模型的方法通常是经验主义的。也就是说,我们观察过程,绘制数据并注意到它们遵循一定的模式。例如,我们的客户可能观察......
  • 多项式
    很多证明需要用到积分知识,所以只有结论和代码一、多项式求导$F'(x)=\sum_{i=0}a_{i+1}\times(i+1)x$点击查看代码inlinevoiddao(int*g,int*f){for(inti=0;i<n;++i)g[i]=f[i+1]*(i+1)%mod;}二、多项式求积分求导逆运算$F'(x)=\sum_{i=1}a_{i-1}\times\fr......
  • 【板子】线性基
    //lgp3812#include<bits/stdc++.h>usingnamespacestd;#definellunsignedlonglonglld[100];intn;voidInsert(llx){ for(inti=62;i>=1;i--) { if(!(x>>(i-1)))continue; if(!d[i]) { d[i]=x; return; } else { ......
  • 【板子】后缀自动机(SAM)
    //lg3804//Copyrightyeyou26//注意:这道题不是纯纯的后缀自动机,main函数有一点额外处理#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineN(int(2e6+6))intfa[N];intch[N][28];intlen[N];intcnt[N];llans;intidx=1;intnp=1;str......
  • 【板子】冒泡/选择/插入 排序
    #include<bits/stdc++.h>usingnamespacestd;#defineN101inta[N];voidsort_mp(){for(inti=1;i<100;i++){for(intj=1;j<100;j++){if(a[j]>a[j+1]){swap(a[j],a[j+1]);......
  • 【板子】高斯约旦消元法(可判解)
    //lg2455#include<bits/stdc++.h>usingnamespacestd;constdoubleeps=0.000001;constintN=105;doublea[N][N];intn;intnowline=1;//存储当前行voidGaussJordan(){ for(inti=1;i<=n;i++)//枚举列若方程有唯一解则与枚举行列等效 { intmxline=no......
  • 【板子】快读/快写
    //double快读inlinevoidReadouble(double&ans){ ans=0; doubley=1.0; boolflag=0; charch=getchar(); while(!isdigit(ch)&&~ch) { flag|=(ch=='-'); ch=getchar(); } while(isdigit(ch)&&~ch) { ans=ans*10+(ch^48);......
  • 【板子】快速排序
    #include<bits/stdc++.h>usingnamespacestd;inta[114514];voidQuicksort(intl,intr);intmain(){freopen("working.in","r",stdin);freopen("working.out","w",stdout);intn;cin>>n;......
  • 【板子】归并排序
    #include<bits/stdc++.h>usingnamespacestd;constintN=1e6+6;intn;inta[N];intb[N];voidMergesort(intl,intr);longlongcnt;intmain(){freopen("working.in","r",stdin);freopen("working.out",&......