【UOJ 34】多项式乘法

 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 }