FFT板子

woc......FFT这玩意儿真坑......

一上午除了打了几遍板子什么也没干......真是废了......

你要加油啊......

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 const double pi=acos(-1.0),eps=1e-;

 struct Complex{

     double a,b;

     Complex(double a=0.0,double b=0.0):a(a),b(b){}

     Complex operator+(const Complex &x)const{return Complex(a+x.a,b+x.b);}

     Complex operator-(const Complex &x)const{return Complex(a-x.a,b-x.b);}

     Complex operator*(const Complex &x)const{return Complex(a*x.a-b*x.b,a*x.b+b*x.a);}

 }A[maxn],B[maxn];

 void FFT(Complex*,int,int);

 int n,m,N=;

 int main(){

     scanf("%d%d",&n,&m);

     n++;m++;

     while(N<n+m)N<<=;

     for(int i=;i<n;i++)scanf("%lf",&A[i].a);

     for(int i=;i<m;i++)scanf("%lf",&B[i].a);

     FFT(A,N,);

     FFT(B,N,);

     for(int i=;i<N;i++)A[i]=A[i]*B[i];

     FFT(A,N,-);

     for(int i=;i<n+m-;i++)printf("%d ",(int)(A[i].a+eps));

     return ;

 }

 void FFT(Complex *A,int n,int tp){

     for(int i=,j=;i<n-;i++){

         int k=N;

         do{

             k>>=;

             j^=k;

         }while(j<k);

         if(i<j)swap(A[i],A[j]);

     }

     for(int k=;k<=n;k<<=){

         Complex wn(cos(-tp**pi/k),sin(-tp**pi/k));

         for(int i=;i<n;i+=k){

             Complex w(1.0,0.0);

             for(int j=;j<(k>>);j++,w=w*wn){

                 Complex a(A[i+j]),b(w*A[i+j+(k>>)]);

                 A[i+j]=a+b;

                 A[i+j+(k>>)]=a-b;

             }

         }

     }

     if(tp<)for(int i=;i<n;i++)A[i].a/=n;

 }

挖个大坑：

COGS2216 你猜是不是KMP