代码

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cctype>

using namespace std;

int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m;

const long double PI=acos(-1.0);

struct Complex
{
    long double x,y;
}a[4200000],b[4200000];

Complex operator + (Complex a,Complex b)
{
    return {a.x+b.x,a.y+b.y};
}

Complex operator - (Complex a,Complex b)
{
    return {a.x-b.x,a.y-b.y};
}

Complex operator * (Complex a,Complex b)
{
    return {a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}

int lim=1,l,r[4200000];

void FFT(Complex *A,int type)
{
    for (int i=0;i<lim;i++)
        if (i<r[i])
            swap(A[i],A[r[i]]);
    for (int mid=1;mid<lim;mid<<=1)
    {
        Complex Wn={cos(PI/mid),type*sin(PI/mid)};
        for (int j=0;j<lim;j+=(mid<<1))
        {
            Complex W={1,0};
            for (int k=0;k<mid;k++)
            {
                Complex x=A[j+k],y=W*A[j+mid+k];
                A[j+k]=x+y;
                A[j+mid+k]=x-y;
                W=W*Wn;	
            } 
        }
    }
}

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 (lim<=n+m)
    {
        lim<<=1;
        l++;
    }
    for (int i=0;i<lim;i++)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    FFT(a,1);
    FFT(b,1);
    for (int i=0;i<=lim;i++)
        a[i]=a[i]*b[i];
    FFT(a,-1);
    for (int i=0;i<=n+m;i++)
        printf("%d ",(int)(a[i].x/lim+0.5));
    return 0;
}

评测结果