萌新的多项式学习笔记(板子)
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