代码

#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],W[N];
int s,R[N];
void DFT(cp *a,int p) {
    For(i,0,s-1) if(i<R[i]) swap(a[i],a[R[i]]);
    W[0]=(cp){1,0};
    for(register int i=1;i<s;i<<=1) {
        cp wn=(cp){cos(pi/i),p*sin(pi/i)};
        for(register int j=i-2;j>=0;j-=2) W[j+1]=wn*(W[j]=W[j>>1]);
        for(register int j=0;j<s;j+=i<<1) {
            cp *p=a+j,*q=a+i+j;
            For(k,0,i-1) {
                cp x=W[k]*q[k];
                q[k]=p[k]-x;
                p[k]=p[k]+x;
            }
        }
    }
}
int F[N],G[N],a,b;
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) s<<=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,1);
	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;
}

评测结果