代码

#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;
			#define H(k) {cp x=W[k]*Q[k];Q[k]=P[k]-x;P[k]=P[k]+x;}
			if(i<8) For(k,0,i-1) H(k)
			else for(register int k=0;k<i;k+=8) {H(k) H(k+1) H(k+2) H(k+3) H(k+4) H(k+5) H(k+6) H(k+7)}
		}
	if(o) {
		reverse(A+1,A+s);
	}
}
char iF[10000007],*p1=iF,*p2=iF,oF[10000007],*p3=oF;
#define GE c=(p1==p2&&(p2=(p1=iF)+fread(iF,1,10000000,stdin),p1==p2)?EOF:*p1++)
#define PU(x) (*p3++=x)
void rd(int &x) {
    x=0; char GE;
    while(!isdigit(c)) GE;
    while(isdigit(c)) x=x*10+(c^48),GE;
}
void pt(int x) {
	if(!x) return;
	pt(x/10),PU(x%10^48);
}
void wt(int x) {
	if(!x) PU(48);
	else pt(x);
}
int main () {
	rd(a),rd(b),++a,++b;
	For(i,0,a-1) rd(F[i]);
	For(i,0,b-1) rd(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) wt(F[i]),PU(' ');
	fwrite(oF,1,p3-oF,stdout);
	return 0;
}

评测结果