代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using std::swap;

const double Pi=M_PI;
const int maxn=1e7+100;

int limit=1,l=0;
int r[maxn];

struct complex
{
    double real,imag;
    complex(double r=0,double i=0):real(r),imag(i){};
    complex operator+ (const complex& c)
    {
        return complex(real+c.real,imag+c.imag);
    }
    complex operator- (const complex& c)
    {
    	return complex(real-c.real,imag-c.imag);
    }
    complex operator* (const complex& c)
    {
    	return complex(real*c.real-c.imag*imag,real*c.imag+c.real*imag);
    }
    void operator*= (const complex& c)
    {
    	double t=real*c.real-c.imag*imag;
    	imag=real*c.imag+c.real*imag;
    	real=t;
    }
};

inline void DFT(complex* A,int type)
{
    for (int i=0;i<limit;++i)
    	if (i<r[i]) swap(A[i],A[r[i]]);
    for (int mid=1;mid<limit;mid<<=1)
    {
    	complex wn(cos(Pi/mid),type*sin(Pi/mid));
    	for (int R=mid<<1,j=0;j<limit;j+=R)
    	{
    		complex w(1,0);
    		for (int k=0;k<mid;++k,w*=wn)
    		{
    			complex x=A[j+k],y=A[j+k+mid]*w;
    			A[j+k]=x+y;
    			A[j+k+mid]=x-y;
    		}
    	}
    }
}

//#define DEBUG 

int main()
{
    static complex a[maxn],b[maxn];
    int n,m;
    scanf("%d%d",&n,&m);
    while (limit<=(n+m)) limit<<=1,++l;
    for (int i=0;i<=n;++i)
        scanf("%lf",&a[i].real);
    for (int i=0;i<=m;++i)
        scanf("%lf",&b[i].real);
    for (int i=0;i<limit;++i)
    	r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    DFT(a,1);DFT(b,1);
    for (int i=0;i<=limit;++i)
        a[i]*=b[i];
    DFT(a,-1);
    for (int i=0;i<=n+m;++i)
        printf("%d ",(int)(a[i].real/limit+0.4));
}

评测结果