FFT我啥都不会，先坑着
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 using namespace std; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 inline int read(){ 9 #define num ch-'0' 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getc())) 12 (ch=='-')&&(flag=true); 13 for(res=num;isdigit(ch=getc());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 char sr[1<<21],z[20];int C=-1,Z; 19 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 20 inline void print(int x){ 21 if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 22 while(z[++Z]=x%10+48,x/=10); 23 while(sr[++C]=z[Z],--Z);sr[++C]=' '; 24 } 25 const int N=1e7+5;const double Pi=acos(-1.0); 26 struct complex{ 27 double x,y; 28 complex(double xx=0,double yy=0){x=xx,y=yy;} 29 inline complex operator +(complex b){return complex(x+b.x,y+b.y);} 30 inline complex operator -(complex b){return complex(x-b.x,y-b.y);} 31 inline complex operator *(complex b){return complex(x*b.x-y*b.y,x*b.y+y*b.x);} 32 }a[N],b[N]; 33 int n,m,l,r[N],limit=1; 34 void FFT(complex *A,int type){ 35 for(int i=0;i<limit;++i) 36 if(i<r[i]) swap(A[i],A[r[i]]); 37 for(int mid=1;mid<limit;mid<<=1){ 38 complex Wn(cos(Pi/mid),type*sin(Pi/mid)); 39 for(int R=mid<<1,j=0;j<limit;j+=R){ 40 complex w(1,0); 41 for(int k=0;k<mid;++k,w=w*Wn){ 42 complex x=A[j+k],y=w*A[j+mid+k]; 43 A[j+k]=x+y,A[j+mid+k]=x-y; 44 } 45 } 46 } 47 } 48 int main(){ 49 // freopen("testdata.in","r",stdin); 50 n=read(),m=read(); 51 for(int i=0;i<=n;++i) a[i].x=read(); 52 for(int i=0;i<=m;++i) b[i].x=read(); 53 while(limit<=n+m) limit<<=1,++l; 54 for(int i=0;i<limit;++i) 55 r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); 56 FFT(a,1),FFT(b,1); 57 for(int i=0;i<=limit;++i) a[i]=a[i]*b[i]; 58 FFT(a,-1); 59 for(int i=0;i<=n+m;++i) 60 print((int)(a[i].x/limit+0.5)); 61 Ot(); 62 return 0; 63 }