代码

#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
using namespace std;

const int N=2000010;
const double pi=acos(-1.);
char s1[N],s2[N];
int n,m,L,x,tmp[10],rev[N];
struct C{ double x,y; }a[N],b[N];

C operator +(const C &a,const C &b){ return (C){a.x+b.x,a.y+b.y}; }
C operator -(const C &a,const C &b){ return (C){a.x-b.x,a.y-b.y}; }
C operator *(const C &a,const C &b){ return (C){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x}; }

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

void write(int x){
	if (x<0) putchar('-'),x=-x;
	if (!x) putchar('0');
	int tot=0;
	while (x) tmp[++tot]=x%10,x/=10;
	for (int i=tot; i; i--) putchar(x+'0');
}

void FFT(C a[],int f){
    rep(i,0,n-1) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int i=1; i<n; i<<=1){
        C wn=(C){cos(pi/i),f*sin(pi/i)};
        for (int p=i<<1,j=0; j<n; j+=p){
            C w=(C){1,0};
            for (int k=0; k<i; k++,w=w*wn){
                C x=a[j+k],y=w*a[i+j+k]; a[j+k]=x+y; a[i+j+k]=x-y;
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    rep(i,0,n) scanf("%lf",&a[i].x);
    rep(i,0,m) scanf("%lf",&b[i].x);
    m=n+m; for (n=1; n<=m; n<<=1) L++;
    rep(i,0,n-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
    rep(i,0,n) a[i]=(C){a[i].x+b[i].x,a[i].x-b[i].x};
    FFT(a,1);
    rep(i,0,n-1) a[i]=a[i]*a[i];
    FFT(a,-1);
    rep(i,0,m) printf("%d ",(int)(a[i].x/n/4+0.5));
    return 0;
}

评测结果