代码

#include<bits/stdc++.h>
using namespace std;
const double pi=3.1415926535;
struct comp
{
	double x,y;
	comp operator+(comp b) {return (comp){x+b.x,y+b.y};}
	comp operator-(comp b) {return (comp){x-b.x,y-b.y};}
	comp operator*(comp b) {return (comp){x*b.x-y*b.y,x*b.y+y*b.x};}
}a[400005],b[400005];int n,m,T,t,r[400005];
inline void FFT(int n,comp *a,int fla)
{
	for(int i=0;i<n;i++) if(r[i]<i) swap(a[i],a[r[i]]);
	for(int mid=1;mid<n;mid<<=1)
	{
		comp wn=(comp){cos(pi/mid),fla*sin(pi/mid)},w;
		for(int i=0,k;i<n;i+=(mid<<1))
			for(k=0,w=(comp){1,0};k<mid;k++,w=w*wn)
				{comp x=a[i+k],y=w*a[i+mid+k];a[i+k]=x+y,a[i+mid+k]=x-y;}
	}
}
int main()
{
	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);
	T=1,t=0;while(T<=n+m) T<<=1,t++;
	for(int i=0;i<T;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(t-1));
	FFT(T,a,1),FFT(T,b,1);for(int i=0;i<T;i++) a[i]=a[i]*b[i];
	FFT(T,a,-1);for(int i=0;i<=n+m;i++) printf("%d%c",(int)(a[i].x/T+0.5),i==n+m?'\n':' ');
	return 0;
}

评测结果