1. acos要用
3. 要改成迭代的
1 #include <cstdio>
2 #include <cmath>
3 #include <complex>
4 #include <iostream>
5 using namespace std;
6 #define PI 3.14159265
7 //const double PI =acos(-1);
8 int n,m;
9 complex<double> a[300000+1],b[300000+1];
10
11 void FFT(complex<double> x[],int lenth,int type)
12 {
13 if(lenth==1) return ;
14 complex<double> p[lenth/2],q[lenth/2];
15 for(int i=0;i<lenth;i++)
16 if(i&1) p[i/2]=x[i];
17 else q[i/2]=x[i];
18 FFT(q,lenth/2,type);
19 FFT(p,lenth/2,type);
20 complex <double> wn(cos(2*PI/lenth),sin(type*2*PI/lenth)),t,w(1,0);
21 for(int i=0;i<lenth/2;i++)
22 {
23 t=w*p[i];
24 x[i]=q[i]+t;
25 x[i+lenth/2]=q[i]-t;
26 w*=wn;
27 }
28 }
29 int main()
30 {
31 scanf("%d %d",&n,&m);int tmp;
32
33 for(int i=0;i<=n;i++) scanf("%d",&tmp),a[i]=tmp;
34 for(int i=0;i<=m;i++) scanf("%d",&tmp),b[i]=tmp;
35 m+=n;m++;
36 n=1;
37 for(;n<m;n*=2);
38 FFT(a,n,1);
39 FFT(b,n,1);
40 for(int i=0;i<n;i++) a[i]*=b[i];
41 FFT(a,n,-1);
42 for(int i=0;i<m;i++) printf("%d ",(int)(a[i].real()/n+0.5));
43 return 0;
44 }