#34. 多项式乘法

 1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <iostream> 6 #include <algorithm> 7  8 const int MAXN=270000; 9 const int DFT=1;10 const int IDFT=-1;11 const double PI=acos(-1);12 13 struct Complex{14     double real;15     double imag;16     Complex(double r=0,double i=0){17         this->real=r;18         this->imag=i;19     }20 };21 Complex operator+(Complex a,Complex b){22     return Complex(a.real+b.real,a.imag+b.imag);23 }24 Complex operator-(Complex a,Complex b){25     return Complex(a.real-b.real,a.imag-b.imag);26 }27 Complex operator*(Complex a,Complex b){28     return Complex(a.real*b.real-a.imag*b.imag,a.real*b.imag+a.imag*b.real);29 }30 31 Complex a[MAXN],b[MAXN],c[MAXN];32 33 int n;             //Length of a34 int m;             //Length of b35 int bln=1;         //Binary Length36 int bct;           //Bit Count37 int len;           //Length Sum38 int rev[MAXN];     //Binary Reverse Sort39 40 void Initialize();41 void FFT(Complex*,int,int);42 43 int main(){44     Initialize();45     FFT(a,bln,DFT);46     FFT(b,bln,DFT);47     for(int i=0;i<=bln;i++){48         c[i]=a[i]*b[i];49     }50     FFT(c,bln,IDFT);51     for(int i=0;i<=len;i++){52         printf("%d ",int(c[i].real/bln+0.5));53     }54     putchar(‘\n‘);55     return 0;56 }57 58 void FFT(Complex* a,int len,int opt){59     for(int i=0;i<len;i++)60         if(i<rev[i])61             std::swap(a[i],a[rev[i]]);62     for(int i=1;i<len;i<<=1){63         Complex wn=Complex(cos(PI/i),opt*sin(PI/i));64         int step=i<<1;65         for(int j=0;j<len;j+=step){66             Complex w=Complex(1,0);67             for(int k=0;k<i;k++,w=w*wn){68                 Complex x=a[j+k];69                 Complex y=w*a[j+k+i];70                 a[j+k]=x+y;71                 a[j+k+i]=x-y;72             }73         }74     }75 }76 77 void Initialize(){78     scanf("%d%d",&n,&m);79     len=n+m;80     while(bln<=len){81         bct++;82         bln<<=1;83     }84     for(int i=0;i<bln;i++){85         rev[i]=(rev[i>>1]>>1)|((i&1)<<(bct-1));86     }87     for(int i=0;i<=n;i++){88         scanf("%lf",&a[i].real);89     }90     for(int i=0;i<=m;i++){91         scanf("%lf",&b[i].real);92     }93 }