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

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int N=5e6+7;
const double PI=acos(-1);

int n,m,res,ans[N],limit=1,R[N],L;

inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

struct complex
{
    double x,y;
    complex(double x=0,double y=0):x(x),y(y){}
}a[N],b[N];

complex operator*(complex aa,complex bb){
    return complex(aa.x*bb.x-aa.y*bb.y,aa.x*bb.y+aa.y*bb.x);
}

complex operator-(complex aa,complex bb){
    return complex(aa.x-bb.x,aa.y-bb.y);
}

complex operator+(complex aa,complex bb){
    return complex(aa.x+bb.x,aa.y+bb.y);
}

void fft(complex *A,int type){
    for(int i=0;i<limit;++i){if(i<R[i])swap(A[i],A[R[i]]);}
    for(int mid=1;mid<limit;mid<<=1){
        complex wn(cos(PI/mid),type*sin(PI/mid));
        for(int len=mid<<1,pos=0;pos<limit;pos+=len){
            complex w(1,0);
            for(int k=0;k<mid;++k,w=w*wn){
                complex x=A[pos+k];
                complex y=w*A[pos+mid+k];
                A[pos+k]=x+y;
                A[pos+mid+k]=x-y;
            }
        }
    }
    if(type==1)return ;
    for(int i=0;i<=limit;++i){
        a[i].x/=limit;
    }
}

int main(){
    n=read(),m=read();
    for(int i=0;i<=n;++i)a[i].x=read();
    for(int i=0;i<=m;++i)b[i].x=read();
    while(limit<=n+m){
        limit<<=1,L++;
    }
    for(int i=0;i<limit;++i){
        R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
    }
    fft(a,1);
    fft(b,1);
    for(int i=0;i<=limit;++i)a[i]=a[i]*b[i];
    fft(a,-1);
    for(int i=0;i<=n+m;++i){
        printf("%d ",(int)(a[i].x+0.5));
    }
}