代码

#include<bits/stdc++.h>
using namespace std;

int n,m,i,j,len;
double pi=acos(-1);
complex<double> w[5000000],f[5000000],g[5000000];
int rev[5000000],bit;
inline void getrev(int n){for(i=0;i<(1<<n);i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));}
void fft(complex<double> *a,int n,int x)
{
	for(int i=0;i<n;i++)if(rev[i]>i)swap(a[i],a[rev[i]]);
	for(int i=1;i<n;i<<=1)
	{
		for(int j=0;j<i;j++)w[j]=complex<double>(cos(pi*j/i),sin(pi*j/i)*(x?-1:1));
		for(int j=0;j<n;j+=(i<<1))
			for(int k=j;k<j+i;k++)
			{
				complex<double> x=a[k],y=a[k+i]*w[k-j];
				a[k]=x+y,a[k+i]=x-y;
			}
	}
	if(x)for(int i=0;i<n;i++)a[i]/=n;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;i++)scanf("%lf",&f[i].real());
	for(i=0;i<=m;i++)scanf("%lf",&g[i].real());
	len=1;
	for(;len<m+n+1;len=len<<1)bit++;getrev(bit);
	fft(f,len,0);fft(g,len,0);
	for(i=0;i<len;i++)f[i]*=g[i];
	fft(f,len,1);
	for(i=0;i<=n+m;i++)printf("%d ",(int)(f[i].real()+0.5));
	return 0;
}

评测结果