代码

#include<stdio.h>
#include<math.h>
#define abs(x) ((x)<0?-(x):(x))
#define TINY (1e-8)
typedef double f12b;
f12b Pi;
int n,m,i,j,k,lg,ni;
int a[3000086],b[3000086];
struct abi{
	f12b a,b;
}u[3000086];
inline abi add(abi x,abi y){
	x.a+=y.a;
	x.b+=y.b;
	return x;
}inline abi sub(abi x,abi y){
	x.a-=y.a;
	x.b-=y.b;
	return x;
}abi mul(abi x,abi y){
	abi r;
	r.a=x.a*y.a-x.b*y.b;
	r.b=x.a*y.b+x.b*y.a;
	return r;
}inline abi posi(f12b g){
	abi r;
	r.a=cos(g);
	r.b=sin(g);
	return r;
}int getint(f12b g){
	int r=g;
	f12b p=r;
	if(g-p>=0.5)++r;
	if(p-g>=0.5)--r;
	return r;
}

void fft(int *s,int *s2,abi *t,int l){
	for(i=0;i<l;++i){
		for(j=k=0;j<lg;++j)
		if((i>>j)&1)k|=1<<(lg-j-1);
		t[k].a=s[i];
		t[k].b=s2[i];
	}f12b gi=Pi;
	abi ca,cb;
	int u;
	for(j=0;j<lg;++j){
		for(i=k=0;i<l;++i)
		if((i>>j)&1){
			i+=(1<<j)-1;
			k=0;
		}else{
			++k;
			u=i|(1<<j);
			ca=t[i];
			cb=mul(posi(k*gi),t[u]);
			t[i]=add(ca,cb);
			t[u]=sub(ca,cb);
		}gi/=2;
	}
}void ift(abi *s,int *t,int l){
	f12b gi=-Pi;
	for(j=1;j<lg;++j)gi/=2;
	abi ca,cb;
	int u;
	for(j=lg-1;j>=0;--j){
		for(i=k=0;i<l;++i)
		if((i>>j)&1){
			i+=(1<<j)-1;
			k=0;
		}else{
			++k;
			u=i|(1<<j);
			ca=add(s[i],s[u]);
			cb=mul(sub(s[i],s[u]),{0.5,0});
			s[i].a=ca.a/2;
			s[i].b=ca.b/2;
			s[u]=mul(posi(k*gi),cb);
		}gi*=2;
	}for(i=0;i<l;++i){
		for(j=k=0;j<lg;++j)
		if((i>>j)&1)k|=1<<(lg-j-1);
		t[i]=getint(s[k].b/2);
	}
}int main(){
//	freopen("P3803.in","r",stdin);
//	freopen("P3803.out","w",stdout);
	Pi=3.141592653589;
	scanf("%d%d",&n,&m);
	++n;
	++m;
	for(i=0;i<n;++i)scanf("%d",a+i);
	for(i=0;i<m;++i)scanf("%d",b+i);
	while((1<<lg)<(n+m-1))++lg;
	ni=1<<lg;
	fft(a,b,u,ni);
	for(i=0;i<ni;++i)u[i]=mul(u[i],u[i]);
	ift(u,a,ni);
	for(i=0;i<n+m-1;++i)printf("%d ",a[i]);
	return 0;
}

评测结果