FFT模板

const double pi=acos(-1); struct cplx{ double r,i;//r为系数的实部，i为虚部。 cplx(double r=0,double i=0):r(r),i(i){} cplx operator +(const cplx &a)const {return cplx(r+a.r,i+a.i);} cplx operator -(const cplx &a)const{ return cplx(r-a.r,i-a.i);} cplx operator *(const cplx &a)const {return cplx(r*a.r-i*a.i,r*a.i+i*a.r);} }f1[maxn*4],f2[maxn*2],res[maxn*4]; void rader(cplx *f,int len){ int j=len>>1; for(int i=1;i<len-1;++i){ if(i<j)swap(f[i],f[j]); int k=len>>1; while(j>=k){ j-=k; k>>=1; } if(j<k)j+=k; } } void FFT(cplx *f,int len,int t){ rader(f,len); for(int h=2;h<=len;h<<=1){ cplx wn(cos(-t*2*pi/h),sin(-t*2*pi/h)); for(int j=0;j<len;j+=h){ cplx e(1,0); for(int k=j;k<j+h/2;++k){ cplx u=f[k]; cplx v=e*f[k+h/2]; f[k]=u+v; f[k+h/2]=u-v; e=e*wn; } } } if(t==-1)for(int i=0;i<len;i++)f[i].r/=len; } void Conv(cplx *a,cplx *b,int len){ FFT(a,len,1); FFT(b,len,1); for(int i=0;i<len;++i)a[i]=a[i]*b[i]; FFT(a,len,-1); }//a为第一个二项式系数，b为第二个二项式系数，len为长度。len的计算方法如下:设原本的二项式长度为n，len=pow(2,k)>n的第一个k的值