代码

#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
int read()
{
	char x=getchar();int ans=0;
	while(!isdigit(x)) x=getchar();
	while(isdigit(x)) ans=ans*10+x-'0',x=getchar();
	return ans;
}
struct comp
{
	double x,y;
	comp(double _x=0,double _y=0)
	{
		x=_x,y=_y;
	}
}f[4000005],g[4000005];
int r[4000005],n,m;
comp operator+(comp a,comp b)
{
	return comp(a.x+b.x,a.y+b.y);
}
comp operator-(comp a,comp b)
{
	return comp(a.x-b.x,a.y-b.y);
}
comp operator*(comp a,comp b)
{
	return comp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
void fft(comp *f,int len,int flag)
{
	for (int i=0;i<len;i++)
		if (i<r[i]) swap(f[i],f[r[i]]);
	for (int mid=1;mid<len;mid<<=1)
	{
		comp tmp=comp(cos(pi/mid),flag*sin(pi/mid));
		for (int rr=mid<<1,j=0;j<len;j+=rr)
		{
			comp tmpp=comp(1,0);
			for (int k=0;k<mid;k++,tmpp=tmpp*tmp)
			{
				comp x=f[j+k],y=tmpp*f[j+mid+k];
				f[j+k]=x+y;
				f[j+mid+k]=x-y;
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for (int i=0;i<=n;i++)
		scanf("%lf",&f[i].x);
	for (int i=0;i<=m;i++)
		scanf("%lf",&g[i].x);
	int nn=1,cntt=0;
	while(nn<=n+m) nn<<=1,cntt++;
	for (int i=0;i<nn;i++)
		r[i]=(r[i>>1]>>1)|((i&1)<<(cntt-1));
	fft(f,nn,1);fft(g,nn,1);
	for (int i=0;i<=nn;i++)
		f[i]=f[i]*g[i];
	fft(f,nn,-1);
	for (int i=0;i<=n+m;i++)
		printf("%d ",(int)(f[i].x/nn+0.5));
	return 0;
}

评测结果