代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
using namespace std;
inline int read()
{
	int s=0,w=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
	while(isdigit(c)){s=(s<<3)+(s<<1)+c-'0',c=getchar();}
	return s*w;
}
typedef double db;
const db pi=acos(-1.0);
const int MAXN=270010;
#define rg register int
struct Complex
{
	db x,y;
	Complex(db _x=0,db _y=0):x(_x),y(_y){}
	friend Complex operator+(const Complex &A,const Complex &B){return Complex(A.x+B.x,A.y+B.y);}
	friend Complex operator-(const Complex &A,const Complex &B){return Complex(A.x-B.x,A.y-B.y);}
	friend Complex operator*(const Complex &A,const Complex &B){return Complex(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);}
};
int pos[MAXN],limit=1,len;
inline void FFT(Complex *A,int type)
{
	for(rg i=0;i<limit;i++)
		if(i<pos[i])swap(A[i],A[pos[i]]);
	for(rg mid=1;mid<limit;mid<<=1)
	{
		Complex wn(cos(pi/mid),type*sin(pi/mid));
		for(rg j=0;j<limit;j+=(mid<<1))
		{
			Complex w(1,0);
			for(rg k=0;k<mid;k++,w=w*wn)
			{
				Complex a=A[j+k],b=w*A[j+mid+k];
				A[j+k]=a+b;
				A[j+mid+k]=a-b;
			}
		}
	}
}
int n,m;
Complex A[MAXN],B[MAXN];
int main()
{
	n=read(),m=read();
	for(rg i=0;i<=n;i++)A[i].x=read();
	for(rg i=0;i<=m;i++)B[i].x=read();
	while(limit<=m+n)limit<<=1,len++;
	for(rg i=1;i<limit;i++)
		pos[i]=((pos[i>>1]>>1)|(i&1)<<(len-1));
	FFT(A,1),FFT(B,1);
	for(rg i=0;i<limit;i++)A[i]=A[i]*B[i];
	FFT(A,-1);
	for(rg i=0;i<=n+m;i++)
		printf("%d ",(int)(A[i].x/limit+0.5));
}

评测结果