存个板子，完全弄懂之后找机会再写个详解。
1 #include<cstdio> 2 #include<cmath> 3 4 struct cpx 5 { 6 double rl,im; 7 friend cpx operator + (cpx q,cpx w) 8 { 9 return (cpx){q.rl+w.rl,q.im+w.im}; 10 } 11 friend cpx operator - (cpx q,cpx w) 12 { 13 return (cpx){q.rl-w.rl,q.im-w.im}; 14 } 15 friend cpx operator * (cpx q,cpx w) 16 { 17 return (cpx){q.rl*w.rl-q.im*w.im,q.rl*w.im+q.im*w.rl}; 18 } 19 friend cpx operator ~ (cpx q) 20 { 21 return (cpx){q.rl,-q.im}; 22 } 23 }urt[2100005][2],af[2100005],bf[2100005]; 24 25 void swap(cpx &q,cpx &w) 26 { 27 cpx t=q;q=w;w=t; 28 } 29 30 int n=1,cnt,na,nb; 31 int r[2100005]; 32 const double pi=acos(-1); 33 34 void prefft() 35 { 36 for(int i=0;i<n;i++) 37 { 38 urt[i][0]=(cpx){cos(2*pi*i/n),sin(2*pi*i/n)}; 39 urt[i][1]=~urt[i][0]; 40 r[i]=(r[i>>1]>>1)|((i&1)<<(cnt-1)); 41 } 42 } 43 44 void fft(cpx *a,int inv) 45 { 46 for(int i=0;i<n;i++)if(i<r[i])swap(a[i],a[r[i]]); 47 for(int l=2;l<=n;l<<=1) 48 { 49 int m=l>>1; 50 for(cpx *p=a;p!=a+n;p+=l) 51 { 52 for(int i=0;i<m;i++) 53 { 54 cpx t=urt[n/l*i][inv]*p[i+m]; 55 p[i+m]=p[i]-t; 56 p[i]=p[i]+t; 57 } 58 } 59 } 60 if(inv)for(int i=0;i<n;i++)a[i].rl/=n; 61 } 62 63 int main() 64 { 65 scanf("%d%d",&na,&nb); 66 while(n<=na+nb)n<<=1,cnt++; 67 for(int i=0;i<=na;i++)scanf("%lf",&af[i].rl); 68 for(int i=0;i<=nb;i++)scanf("%lf",&bf[i].rl); 69 prefft(); 70 fft(af,0); 71 fft(bf,0); 72 for(int i=0;i<n;i++)af[i]=af[i]*bf[i]; 73 fft(af,1); 74 for(int i=0;i<=na+nb;i++)printf("%d ",(int)(af[i].rl+0.5)); 75 return 0; 76 }