代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
double pi(acos(-1));
struct comp {
	double s,x;
	inline comp operator+(const comp&b) const {
		return(comp) {
			s+b.s,x+b.x
		};
	}
	inline comp operator-(const comp&b) const {
		return(comp) {
			s-b.s,x-b.x
		};
	}
	inline comp operator*(const comp&b) const {
		return(comp) {
			s*b.s-x*b.x,s*b.x+b.s*x
		};
	}
	comp (double xx=0,double yy=0) {
		s=xx,x=yy;
	}
} a[3100010];
int n,m;
void DFT(comp a[],int len) {
	if(len<=1)return;
	comp A0[(len>>1)+1],A1[(len>>1)+1];
	for(int i=0; i<=len; i+=2)
		A0[i>>1]=a[i],A1[i>>1]=a[i+1];
	DFT(A0,len>>1);
	DFT(A1,len>>1);
	comp w=(comp) {
		cos(2.0*pi/len),sin(2.0*pi/len)
	};
	comp d=(comp) {
		1.0,0.0
	};
	for(int i=0; i<len/2; i++,d=d*w) {
		a[i]=A0[i]+A1[i]*d;
		a[i+(len>>1)]=A0[i]-A1[i]*d;
	}
	return;
}
void IDFT(comp a[],int len) {
	if(len<=1)return;
	comp A0[(len>>1)+1],A1[(len>>1)+1];
	for(int i=0; i<=len; i+=2)
		A0[i>>1]=a[i],A1[i>>1]=a[i+1] ;
	IDFT(A0,len>>1);
	IDFT(A1,len>>1);
	comp w=(comp) {
		cos(2.0*pi/len),sin(2.0*pi/len)*(-1.0)
	};
	comp d=(comp) {
		1.0,0.0
	};
	for(int i=0; i<len/2; i++,d=d*w) {
		a[i]=A0[i]+A1[i]*d;
		a[i+(len>>1)]=A0[i]-A1[i]*d;
	}
	return;
}
long long int p;
int main() {
	scanf("%d%d",&n,&m);
	for(int i=0; i<=n; i++) {
		int x(0);
		scanf("%d",&x);
		a[i].s=(double)x;
	}
	for(int i=0; i<=m; i++) {
		int x(0);
		scanf("%d",&x);
		a[i].x=(double)x;
	}
	int lenth(1);
	while(lenth<=n+m+2)lenth=lenth<<1;
	DFT(a,lenth);
	for(int i=0; i<lenth; i++) {
		a[i]=a[i]*a[i];
	}
	IDFT(a,lenth);
	for(int i=0; i<lenth; i++)
		a[i].x/=(double)lenth;
	for(int i=0; i<=n+m; i++) {
		printf("%lld ",(long long)(a[i].x/2.0+0.1));
	}
	return 0;
}

评测结果