FFT快速傅里叶变化

纪念人生第一次FFT
前排感谢iamzky，讲解非常详细
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 
 6 const int MAXN=200010;
 7 class BigNum
 8 {
 9 public:
10     double r,i;
11     BigNum(double _r=0.0,double _i=0.0){r=_r;i=_i;}
12     BigNum operator+(const BigNum T){return BigNum(r+T.r,i+T.i);}
13     BigNum operator-(const BigNum T){return BigNum(r-T.r,i-T.i);};
14     BigNum operator*(const BigNum T){return BigNum(r*T.r-i*T.i,r*T.i+i*T.r);};
15 };
16 
17 void Brc(BigNum *T,int N)
18 {
19     int i,j,k;
20     for(i=1,j=N/2;i<N-1;i++)
21     {
22         if(i<j) swap(T[i],T[j]);
23         k=N/2;
24         while(j>=k)
25         {
26             j-=k;
27             k>>=1;
28         }
29         if(j<k) j+=k;
30     }
31 }
32 
33 void FFT(BigNum *T,int N,int flag)
34 {
35     Brc(T,N);
36     for(int i=2;i<=N;i<<=1)
37     {
38         BigNum wn(cos(2*M_PI/i),flag*sin(2*M_PI/i));
39         for(int j=0;j<N;j+=i)
40         {
41             BigNum w(1,0);
42             for(int k=j;k<j+i/2;k++)
43             {
44                 BigNum u=T[k];
45                 BigNum t=w*T[k+i/2];
46                 T[k]=u+t;
47                 T[k+i/2]=u-t;
48                 w=w*wn;
49             }
50         }
51     } 
52     if(flag==-1)
53         for(int i=0;i<N;i++)
54             T[i].r/=N;
55 }
56 
57 string s1,s2;
58 BigNum A[MAXN],B[MAXN],C[MAXN];
59 int a[MAXN],b[MAXN],sum[MAXN];
60 int N;
61 
62 int main()
63 {
64     cin>>s1>>s2;
65     int L1=s1.size();
66     int L2=s2.size();
67     for(N=1;N<max(L1,L2);N<<=1);N<<=1;
68     for(int i=0;i<L1;i++) a[L1-i-1]=s1[i]-'0';
69     for(int i=0;i<L2;i++) b[L2-i-1]=s2[i]-'0';
70     for(int i=0;i<N;i++) A[i]=BigNum(a[i]);
71     for(int i=0;i<N;i++) B[i]=BigNum(b[i]);
72     FFT(A,N,1);FFT(B,N,1);  
73     for(int i=0;i<N;i++)C[i]=A[i]*B[i];
74     FFT(C,N,-1);
75     for(int i=0;i<N;i++)sum[i]=C[i].r+0.5;  
76     for(int i=0;i<N;i++)
77     {  
78         sum[i+1]+=sum[i]/10;  
79         sum[i]%=10;  
80     }  
81     int l=L1+L2-1;  
82     while(sum[l]==0&&l>0)l--;  
83     for(int i=l;i>=0;i--)  
84     cout<<sum[i];
85     return 0;
86 }