代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e6+5;
const double PI=acos(-1.0);
//typedef complex<double> comp;
struct comp
{
	double x,y;
	comp(double xx=0,double yy=0) {x=xx,y=yy;}
}buf[maxn];
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);}

int rev[maxn];
void fft(comp *a,int n,int inv) //inv=1,FFT;inv=-1,IFFT.
{
	for(int i=0;i<n;++i)
		if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int i=2;i<=n;i<<=1)
	{
		comp wn(cos(2*PI/i),sin(2*PI*inv/i));
		for(int j=0;j<n;j+=i)
		{
			comp w(1,0);
			int m=i>>1;
			for(int k=0;k<m;++k,w=w*wn)
			{
				comp tmp=w*a[j+k+m];
				a[j+k+m]=a[j+k]-tmp;
				a[j+k]=a[j+k]+tmp;
			}
		}
	}
}
comp a[maxn],b[maxn];
int main()
{
	int n,m,l=0;
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;++i)
		scanf("%lf",&a[i].x);
	for(int i=0;i<=m;++i)
		scanf("%lf",&b[i].x);
	int lim=1;
	while(lim<=m+n) lim<<=1,++l;
	for(int i=0;i<lim;++i)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	fft(a,lim,1);fft(b,lim,1);
	for(int i=0;i<=lim;++i)
		a[i]=a[i]*b[i];
	fft(a,lim,-1);
	for(int i=0;i<=n+m;++i)
		printf("%d ",(int)(0.5+a[i].x/lim));
	printf("\n");
	return 0;
}

评测结果