代码

#include <stdio.h>
#include <math.h>
#include <algorithm>
#define N 2100000
struct cp {
	double r,i;
	cp(double a=0,double b=0):r(a),i(b){}
};
inline cp operator+(cp a,cp b) {
	return cp(a.r+b.r,a.i+b.i);
}
inline cp operator-(cp a,cp b) {
	return cp(a.r-b.r,a.i-b.i);
}
inline cp operator*(cp a,cp b) {
	return cp(a.r*b.r-a.i*b.i,a.r*b.i+b.r*a.i);
}
int L,rev[N]; cp w0[N],w1[N];
void init() {
	register double D_PI=2*acos(-1),t;
	register int i,j;
	for(i=0;i<1<<L;++i) {
		t=D_PI*i/(1<<L);
		w0[i].r=cos(t);
		w0[i].i=sin(t);
		w1[i].r=w0[i].r;
		w1[i].i=-w0[i].i;
		for(j=0;j<L;++j) rev[i]|=(i>>j&1)<<(L-j-1);
	}
}
void FFT(cp *f,cp *w) {
	register int i,j,k;
	register cp t;
	for(i=0;i<1<<L;++i) if(i<rev[i]) std::swap(f[i],f[rev[i]]);
	for(i=0;i<L;++i) {
		for(j=0;j<1<<L;j+=2<<i) {
			for(k=0;k<1<<i;++k) {
				t=w[k<<L-i-1]*f[j|k|1<<i];
				f[j|k|1<<i]=f[j|k]-t;
				f[j|k]=f[j|k]+t;
			}
		}
	}
}
int main() {
	static cp f[N],g[N];
	register int i,n,m,x;
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;++i) {
		scanf("%d",&x); f[i].r=x;
	}
	for(i=0;i<=m;++i) {
		scanf("%d",&x); g[i].r=x;
	}
	for(L=0;1<<L<n+m+1;++L);
	init();
	FFT(f,w0);
	FFT(g,w0);
	for(i=0;i<1<<L;++i) f[i]=f[i]*g[i];
	FFT(f,w1);
	for(i=0;i<=n+m;++i) {
		printf("%d ",(int)(f[i].r/(1<<L)+.5));
	}
	return 0;
}

评测结果