代码

#include <bits/stdc++.h>

using namespace std;

inline int read()
{
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0' || ch>'9') {if(ch=='-') f=1;ch=getchar();}
	while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}

#define x first
#define y second

typedef pair<int,int> PII;
typedef long long LL;
const int N=3e6+10;
const double PI=acos(-1);

int A,B;
int n,bit;
int rev[N];
struct Complex{
	double x,y;
	Complex operator+(Complex b){return {x+b.x,y+b.y};}
	Complex operator-(Complex b){return {x-b.x,y-b.y};}
	Complex operator*(Complex b){return {x*b.x-y*b.y,x*b.y+y*b.x};}
}a[N],b[N],w[N];

void fft(Complex a[],int inv)
{
	for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
	if(inv==-1) for(int i=0;i<n;i++) w[i].y=-w[i].y;
	for(int d=1,t=n>>1;d<n;d<<=1,t>>=1)
		for(int i=0;i<n;i+=(d<<1))
			for(int j=0;j<d;j++){
				auto tmp=a[i+j+d]*w[t*j];
				a[i+j+d]=a[i+j]-tmp,a[i+j]=a[i+j]+tmp;
			}
	if(inv==-1) for(int i=0;i<n;i++) w[i].y=-w[i].y;
}

int main()
{
	A=read(),B=read();
	for(int i=0;i<=A;i++) a[i].x=read();
	for(int i=0;i<=B;i++) b[i].x=read();
	
	while((1<<bit)<=A+B) bit++; n=1<<bit;
	for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
	for(int i=0;i<n;i++) w[i]={cos(2*PI/n*i),sin(2*PI/n*i)};
	
	fft(a,1),fft(b,1);
	for(int i=0;i<n;i++) a[i]=a[i]*b[i];
	fft(a,-1);
	for(int i=0;i<=A+B;i++) printf("%d ",(int)(a[i].x/n+0.5));
	
	return 0;
}

评测结果