代码

#include<bits/stdc++.h>
#define ll long long
#define re register
#define INF 2147483647
using namespace std;

inline int read()
{
	int f=1,x=0;char s=getchar();
	while(s<'0'||s>'9')
	{
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9')
	{
		x=x*10+s-48;
		s=getchar();
	}
	return f*x;
}

const int N=1350000;
const double pi=acos(-1);

struct CP
{
	double x,y;
	CP(double xx=0,double yy=0){x=xx,y=yy;}	
}f[N<<1],g[N<<1],ans[N<<1];

CP operator + (CP a,CP b) {return CP(a.x+b.x,a.y+b.y);}
CP operator - (CP a,CP b) {return CP(a.x-b.x,a.y-b.y);}
CP operator * (CP a,CP b) {return CP(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}

int rev_len,n,m;
int rev[N<<1];

void getrev(int n)
{
	if(rev_len==n) return;
	rev_len=n;
	for(int i=0;i<n;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0); 
}

void FFT(CP *f,bool flag,int len)
{
	getrev(len);
	for(int i=0;i<len;i++)
		if(i<rev[i]) swap(f[i],f[rev[i]]);
	for(int p=1;p<len;p<<=1)
	{
		CP w(cos(pi/p),sin(pi/p));
		if(!flag) w.y*=-1;
		for(int k=0;k<len;k+=(p<<1))
		{
			CP buf(1,0);
			for(int i=k;i<k+p;i++)
			{
				CP tmp=buf*f[i+p];
				f[i+p]=f[i]-tmp;
				f[i]=f[i]+tmp;
				buf=buf*w;
			}	
		} 
	}
	if(!flag) for(int i=0;i<len;i++) f[i].x/=len;
}

void times(CP *f,CP *g,CP *ans,int n,int m)
{
	int len=1;
	for(;len<=m+n;len<<=1);
	FFT(f,1,len),FFT(g,1,len);
	for(int i=0;i<len;i++) ans[i]=f[i]*g[i];
	FFT(ans,0,len);
}

int main()
{
	n=read(),m=read();
	for(int i=0;i<=n;i++) f[i].x=read();
	for(int i=0;i<=m;i++) g[i].x=read();
	times(f,g,ans,n,m);
	for(int i=0;i<=n+m;i++) printf("%d ",(int)(ans[i].x+0.5));
	return 0;
}

评测结果