代码

#include<bits/stdc++.h>
using namespace std;
typedef double ld;
ld const pi=acos(-1),eps=1e-3;
struct comp
{
    ld a,b;
    friend comp operator + (const comp &x,const comp &y)
    {
        return (comp){x.a+y.a,x.b+y.b};
    }
    friend comp operator - (const comp &x,const comp &y)
    {
        return (comp){x.a-y.a,x.b-y.b};
    }
    friend comp operator * (const comp &x,const comp &y)
    {
        return (comp){x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a};
    }
    comp(double x=0,double y=0){a=x;b=y;}
}a[4000001],w[4000001];
int r[4000001];
void init(int n)
{
    int lim=1;
    while(lim<n)lim<<=1;
    for(int i=1;i<lim;i<<=1)
    {
        comp wn=comp(cos(pi/i),sin(pi/i)),ww=comp(1,0);
        for(int j=0;j<i;j++,ww=ww*wn)w[i+j]=ww;
    }
}
void fft(comp *f,int n,int op)
{
    for(int i=1;i<n;i++)if(i<r[i])swap(f[i],f[r[i]]);
    for(int i=1;i<n;i<<=1)
    for(int j=0;j<n;j+=i<<1)
        for(int k=0;k<i;k++)
        {
            comp x=f[j+k],y=f[j+k+i]*w[i+k];
            f[j+k+i]=x-y;
            f[j+k]=x+y;
        }
    if(op==-1)
    {
        reverse(&f[1],&f[n]);
        for(int i=0;i<n;i++)f[i]=f[i]*comp(0.5/n,0);
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(register int i=0;i<=n;++i)scanf("%lf",&a[i].a);
    for(register int i=0;i<=m;++i)scanf("%lf",&a[i].b);
    m+=n,n=1;
    while(n<=m)n<<=1;
    for(register int i=0;i<n;++i)
        r[i]=(r[i>>1]>>1)|((i&1)?(n>>1):0);
    init(n);
    fft(a,n,1);
    for(register int i=0;i<n;++i)a[i]=a[i]*a[i];
    fft(a,n,-1);
    for(register int i=0;i<=m;++i)printf("%d ",(int)(fabs(a[i].b)+eps));
    return 0;
}

评测结果