1 //UOJ 34 递归版 2 #include<cmath> 3 #include<vector> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<complex> 8 #include<iostream> 9 #include<algorithm>10 #define rep(i,n) for(int i=0;i<n;++i)11 #define F(i,j,n) for(int i=j;i<=n;++i)12 #define D(i,j,n) for(int i=j;i>=n;--i)13 using namespace std;14 const int N=256256;15 void read(int &v){16     v=0;int sign=1; char ch=getchar();17     while(ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) sign=-1; ch=getchar();}18     while(ch>=‘0‘&&ch<=‘9‘){v=v*10+ch-‘0‘; ch=getchar();}19     v*=sign;20 }21 /****************tamplate***********************/22 const double PI=acos(-1);23 typedef complex<double> comp;24 comp a[N],b[N],c[N];25 void FFT(comp a[],int n,int type){26     if (n==1) return;27     int i;28     comp y0[n>>1],y1[n>>1];29     for(int i=0;i<n;i+=2)30         y0[i>>1]=a[i],y1[i>>1]=a[i+1];31     FFT(y0,n>>1,type); FFT(y1,n>>1,type);32     comp w0( cos(type*2*PI/n) , sin(type*2*PI/n) ), w(1,0);33     for(i=0;i<(n>>1);i++,w*=w0)34         a[i]=y0[i]+w*y1[i],a[i+(n>>1)]=y0[i]-w*y1[i];35 }36 int main(){37     int i,temp,n,m;38     read(n); read(m);39     int x;40     F(i,0,n) read(x),a[i].real()=x;41     F(i,0,m) read(x),b[i].real()=x;42     for(temp=1;temp<=m+n;temp<<=1);43     FFT(a,temp,1); FFT(b,temp,1);44     rep(i,temp) c[i]=a[i]*b[i];45     FFT(c,temp,-1);46     for(int i=0;i<=m+n;++i)47         printf("%d ",int(c[i].real()/temp+0.5));48     puts("");49     return 0;50 }