代码

#pragma GCC optimize("-O3")
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-ffast-math")
#include <cstdio>
#include <cmath>
#include <cctype>

const double Pi=acos(-1.0);
const int maxn=4e6+100;

double q[maxn];
int limit=1,rev[maxn];

struct Complex
{
    double real,imag;
    Complex(double real,double imag):real(real),imag(imag){}
    Complex(){}
    Complex conj();
}w[maxn],winv[maxn],A[maxn];

inline Complex Complex::conj(){return Complex(real,-imag);}
inline Complex operator+(const Complex& a,const Complex& b){return Complex(a.real+b.real,a.imag+b.imag);}
inline Complex operator-(const Complex& a,const Complex& b){return Complex(a.real-b.real,a.imag-b.imag);}
inline Complex operator*(const Complex& a,const Complex& b){return Complex(a.real*b.real-a.imag*b.imag,a.real*b.imag+a.imag*b.real);}

template<typename T>
inline void swap(T& a,T& b){T t=a;a=b;b=t;}

inline void DFT(Complex* A,Complex* w,int limit)
{
    for (register int i=0;i<limit;++i)
        if (i<rev[i]) swap(A[i],A[rev[i]]);
    for (register int mid=1;mid<limit;mid<<=1)
        for (register int R=mid<<1,j=0;j<limit;j+=R)
            for (register int k=0;k<mid;++k)
            {
                Complex x=A[j+k],y=w[limit/mid/2*k]*A[j+mid+k];
                A[j+k]=x+y;
                A[j+mid+k]=x-y;
            }
}

inline void prework(int n)
{
    int l=0;
    while (limit<=(n<<1)+1) limit<<=1,++l;
    for (register int i=0;i<limit;++i)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    for (register int i=0;i<limit;++i) 
        w[i]=Complex(cos(Pi*2/limit*i),sin(Pi*2/limit*i)),winv[i]=w[i].conj();
}

char buf[1<<25],*fs;
#define gc() (*fs++)

inline int gi()
{
    register char ch;
    while (!isdigit(ch=gc()));
    int x=ch-48;
    return x;
}

inline int getnm()
{
    register char ch;
    while (!isdigit(ch=gc()));
    register int x=ch-48;
    while (isdigit(ch=gc()))
        x=x*10+ch-48;
    return x;
}

int main()
{
    fread(fs=buf,1,1<<25,stdin);
    int n=getnm(),m=getnm();
    for (register int i=0;i<=n;++i)
        A[i].real=gi();    
    for (register int i=0;i<=m;++i)
        A[i].imag=gi();
    prework(n>=m?n:m);
    DFT(A,w,limit);
    for (register int i=0;i<limit;++i)
        A[i]=A[i]*A[i];
    DFT(A,winv,limit);
    for (register int i=0;i<=n+m;++i)
        printf("%d ",(int)(A[i].imag/2/limit+0.1));
}

评测结果