代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<queue>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#define PI 3.14159265358979323846
using namespace std;

struct Complex
{
    double r,i;
    Complex(double _x=0.0,double _y=0.0) { r=_x; i=_y; }
    Complex operator + (Complex& a) const { return Complex(r+a.r,i+a.i); }
    Complex operator - (Complex& a) const { return Complex(r-a.r,i-a.i); }
    Complex operator * (Complex& a) const { return Complex( r*a.r-i*a.i , r*a.i+i*a.r ); }
};

inline void readx(int& x)
{
    x=0; int k=1; register char ch=0;
    while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

int rev[3000010]={0},revt=0; char revf=0;
inline void btfl(Complex y[],int len)
{
    if (!revf)
    {
        revf=1; revt--;
        for (int i=0;i<len;i++) rev[i]=( rev[i>>1]>>1 | ((i&1)<<revt) );
    }
    for (int i=0;i<len;i++) if (i<rev[i]) swap(y[i],y[rev[i]]);
}

inline void FaFaTa(Complex y[],int len,int mode)
{
    btfl(y,len);
    for (int i=1;i<len;i<<=1)
    {
        Complex wn( cos(PI/i) , mode* sin(PI/i) );
        for (int j=0;j<len;j+=(i<<1))
        {
            Complex w(1,0);
            for (int k=0;k<i;k++,w=w*wn)
            {
                Complex tx=y[j+k],ty=w*y[i+j+k];
                y[j+k]=tx+ty;
                y[i+j+k]=tx-ty;
            }
        }
    }
}

Complex A[3000010],B[3000010];
int n,m,Lim=1;

int main()
{
    readx(n); readx(m); register int cac=0;
    for (int i=0;i<=n;i++) { readx(cac); A[i].r=(double)cac; }
    for (int i=0;i<=m;i++) { readx(cac); B[i].r=(double)cac; }
    while (Lim<=n+m) Lim<<=1,revt++;
    
    FaFaTa(A,Lim,1); FaFaTa(B,Lim,1);
    for (int i=0;i<Lim;i++) A[i]=A[i]*B[i];
    FaFaTa(A,Lim,-1);
    
    for (int i=0;i<=m+n;i++) printf("%d ",(int)(A[i].r/Lim+0.5));
    printf("\n");
    return 0;
}

评测结果