题解 P3803 【【模板】多项式乘法（FFT）】

大菜鸡fks · 2018-12-16 23:21:47 · 题解

算导上都有，原理推导证明讲的很清楚了。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
inline int read(){int x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}
inline void write(int x){if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0');}
inline void writeln(int x){write(x); puts("");}
const int N=2100000;
const double pi=acos(-1.0);
struct complex{
    double x,y;
    complex (double xx=0,double yy=0) {x=xx; y=yy;}
}a[N],b[N];
inline complex operator +(complex A,complex B){return complex(A.x+B.x,A.y+B.y);}
inline complex operator -(complex A,complex B){return complex(A.x-B.x,A.y-B.y);}
inline complex operator *(complex A,complex B){return complex(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);}
int n,m,l,lim,r[N];
inline void init(){
    n=read(); m=read(); lim=1;
    for (int i=0;i<=n;i++) a[i].x=read();
    for (int i=0;i<=m;i++) b[i].x=read();
    while (lim<=n+m) lim<<=1,l++;
    for (int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}
void DFT(complex *A,int opt){
    for (int i=0;i<lim;i++) if (i<r[i]) swap(A[i],A[r[i]]);
    for (int s=1;s<lim;s<<=1){
        complex Wn(cos(pi/s),opt*sin(pi/s));
        for (int i=0;i<lim;i+=s<<1){
            complex w(1,0);
            for (int j=0;j<s;j++,w=w*Wn){
                complex x=A[i+j],y=w*A[i+s+j];
                A[i+j]=x+y; A[i+s+j]=x-y;
            }
        }
    }
}
inline void solve(){
    DFT(a,1); DFT(b,1);
    for (int i=0;i<=lim;i++) a[i]=a[i]*b[i];
    DFT(a,-1);
    for (int i=0;i<=n+m;i++) write(int(a[i].x/lim+0.5)),putchar(' ');
}
int main(){
    init(); solve();
    return 0;
}