代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 6000005;
const double pi = acos(-1.0);

struct comp{
    double r,i;
    comp(double r=0,double i=0):r(r),i(i){}
};
comp operator +(comp x,comp y){
    return comp(x.r+y.r,x.i+y.i);
}
comp operator -(comp x,comp y){
    return comp(x.r-y.r,x.i-y.i);
}
comp operator *(comp x,comp y){
    return comp(x.r*y.r-x.i*y.i,x.r*y.i+x.i*y.r);
}
comp a[maxn],b[maxn],c[maxn];
int res[maxn],r[maxn];

void radar(comp *a,int len){
    int j=len>>1;
    for(int i=1;i<len-1;i++){
        if(i<j) swap(a[i],a[j]);
        int k=len>>1;
        while(k&j){
            j^=k;k>>=1;
        }
        j^=k;
    }
}

void FFT(comp *a,int t,int len){
    //radar(a,len);

    for(int i=0;i<len;i++)
        if(i<r[i])
            swap(a[i],a[r[i]]);

    for(int h=1;h<len;h<<=1){
        comp wn=comp(cos(-t*pi/h),sin(-t*pi/h));
        int step=h*2;
        for(int i=0;i<len;i+=step){
            comp e(1,0);
            for(int j=i;j<i+h;j++){
                comp u=a[j],v=e*a[j+h];
                a[j]=u+v;a[j+h]=u-v;
                e=e*wn;
            }
        }
    }
    if(t==-1){
        for(int i=0;i<len;i++) a[i].r/=len;
    }
}

int main(){

    int n,m,len=1;
    scanf("%d%d",&n,&m);
    int l=0;
    m+=n;
    for(len=1;len<=m;len<<=1)
        l++;
    for(int i=0;i<len;i++)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));

    //while(len<=n+m) len<<=1;
    for(int i=0;i<=n;i++) {
        int x;scanf("%d",&x);a[i]=comp(x,0);
    }
    for(int i=n+1;i<len;i++) a[i]=comp(0,0);
    for(int i=0;i<=m;i++){
        int x;scanf("%d",&x);b[i]=comp(x,0);
    }
    for(int i=m+1;i<len;i++) b[i]=comp(0,0);

    FFT(a,1,len);FFT(b,1,len);
    for(int i=0;i<len;i++) c[i]=a[i]*b[i];
    FFT(c,-1,len);
    for(int i=0;i<=n+m;i++) {
        res[i]=(int)(c[i].r+0.4);
        printf("%d ",res[i]);
    }

    return 0;
}

评测结果