代码

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define For(a,b,c) for(register int a=b;a<=c;++a)
using namespace std;
const int N=270000;
const double pi=acos(-1);
struct cp {
	double x,y;
	cp operator + (const cp &_) {return (cp){x+_.x,y+_.y};}
	cp operator - (const cp &_) {return (cp){x-_.x,y-_.y};}
	cp operator * (const cp &_) {return (cp){x*_.x-y*_.y,x*_.y+y*_.x};}
}A[N],B[N],O[N];
int s,R[N],F[N],G[N],a,b;
void DFT(cp *A,int o=0) {
	For(i,0,s-1) if(i<R[i]) swap(A[i],A[R[i]]);
	for(register int i=1;i<s;i<<=1)
		for(register int j=0;j<s;j+=i<<1) {
			cp *W=O+i,*P=A+j,*Q=A+j+i;
			For(k,0,i-1) {
				cp x=W[k]*Q[k];
				Q[k]=P[k]-x;
				P[k]=P[k]+x;
			}
		}
	if(o) {
		reverse(A+1,A+s);
	}
}
int main () {
	scanf("%d%d",&a,&b),++a,++b;
	For(i,0,a-1) scanf("%d",&F[i]);
	For(i,0,b-1) scanf("%d",&G[i]);
	s=1; while(s<a+b-1) s<<=1;
	cp w=(cp){cos(2*pi/s),sin(2*pi/s)};
	O[s>>1]=(cp){1,0};
	for(int i=(s>>1)+1;i<s;++i) O[i]=O[i-1]*w;
	for(int i=(s>>1)-1;i>0;--i) O[i]=O[i<<1];
	For(i,0,s-1) R[i]=(R[i>>1]>>1)|((i&1)*(s>>1));
	For(i,0,a-1) A[i].x=F[i];
	For(i,0,b-1) A[i].y=G[i];
	DFT(A);
	For(i,0,s-1) A[i]=A[i]*A[i];
	DFT(A,1);
	For(i,0,s-1) F[i]=A[i].y/s/2+0.5;
	For(i,0,a+b-2) printf("%d ",F[i]);
	return 0;
}

评测结果