代码

#include<iostream>
#include<cstdio>
#include<cmath>
#define db double
using namespace std;
const int N=3e6+10;
const db PI=acos(-1.0);
int rev[N];
struct cp
{
	db a,b;
}A[N],B[N];
cp operator + (cp x,cp y)
{
	return (cp){x.a+y.a,x.b+y.b};
}
cp operator - (cp x,cp y)
{
	return (cp){x.a-y.a,x.b-y.b};
}
cp operator * (cp x,cp y)
{
	return (cp){x.a*y.a-x.b*y.b,x.b*y.a+x.a*y.b};
}
void FFT(cp *a,int tp,int n)
{
	for(int i=0;i<n;i++)
		if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int l=1;l<n;l*=2)
	{
		cp w=(cp){cos(PI/(db)(l)),(db)(tp)*sin(PI/(db)(l))};
		for(int i=0;i<n;i+=l*2)
		{
			cp W=(cp){1,0};
			for(int k=0;k<l;k++,W=W*w)
			{
				cp x=a[i+k],y=W*a[i+k+l];
				a[i+k]=x+y,a[i+k+l]=x-y;
			}
		}
	}
}
int main()
{
	int n,m,t=1,O=0;
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++) scanf("%lf",&A[i].a);
	for(int i=0;i<=m;i++) scanf("%lf",&B[i].a);
	while(t<=n+m) t*=2,O++;
	for(int i=0;i<=t;i++)
		rev[i]=(rev[i/2]/2)+(1<<O-1)*(i%2);
	FFT(A,1,t),FFT(B,1,t);
	for(int i=0;i<=t;i++) A[i]=A[i]*B[i];
	FFT(A,-1,t);
	for(int i=0;i<=n+m;i++)
		printf("%d ",(int)(A[i].a/(db)t+0.5));
	return 0;
}

评测结果