【UOJ 34】 #34. 多项式乘法（FFT）

【分析】

　　这个只是用来放模板。。【其实我还没完全懂的。。

迭代代替递归：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<complex>
 8 #define Maxn 262145
 9 #define pi acos(-1)
10 using namespace std;
11 
12 struct P
13 {
14     double x,y;
15     P() {x=y=0;}
16     P(double x,double y):x(x),y(y){}
17     friend P operator + (P x,P y) {return P(x.x+y.x,x.y+y.y);}
18     friend P operator - (P x,P y) {return P(x.x-y.x,x.y-y.y);}
19     friend P operator * (P x,P y) {return P(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);}
20 }a[Maxn],b[Maxn];
21 
22 int nn;
23 int R[Maxn];
24 void fft(P *a,int f)
25 {
26     for(int i=0;i<nn;i++) if(i<R[i]) swap(a[i],a[R[i]]);
27     for(int i=1;i<nn;i<<=1)
28     {
29         P wn(cos(pi/i),f*sin(pi/i));
30         for(int j=0;j<nn;j+=i<<1)
31         {
32             P w(1,0);
33             for(int k=0;k<i;k++,w=w*wn)
34             {
35                 P x=a[j+k],y=w*a[j+k+i];
36                 a[j+k]=x+y;a[j+k+i]=x-y;
37             }
38         }
39     }
40 }
41 int main()
42 {
43     freopen("a.in","r",stdin);
44     freopen("b.out","w",stdout);
45     int n,m;
46     scanf("%d%d",&n,&m);
47     for(int i=0;i<=n;i++) scanf("%lf",&a[i].x);
48     for(int i=0;i<=m;i++) scanf("%lf",&b[i].x);
49     int ll=0;nn=1;
50     while(nn<=n+m) ll++,nn<<=1;
51     for(int i=0;i<nn;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(ll-1));
52     fft(a,1);fft(b,1);
53     for(int i=0;i<=nn;i++) a[i]=a[i]*b[i];
54     fft(a,-1);
55     for(int i=0;i<=n+m;i++) printf("%d ",(int)(a[i].x/nn+0.5));
56     return 0;
57 }

View Code

2017-04-13 16:43:54

【UOJ 34】 #34. 多项式乘法 （FFT）

【UOJ 34】 #34. 多项式乘法（FFT）