代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const double pi=acos(-1);
int n,m,len=1,deg=0;
struct Complex{
	double real,imag;
}f[3000010],buf1,buf2;
Complex operator ~(const Complex &x){
	return (Complex){x.real,-x.imag};
}
Complex operator -(const Complex &x){
	return (Complex){-x.real,-x.imag}; 
}
Complex operator +(const Complex &x,const Complex &y){
	return (Complex){x.real+y.real,x.imag+y.imag};
}
Complex operator -(const Complex &x,const Complex &y){
	return (Complex){x.real-y.real,x.imag-y.imag};
}
Complex operator *(const Complex &x,const Complex &y){
	return (Complex){x.real*y.real-x.imag*y.imag,x.real*y.imag+x.imag*y.real};
}
Complex operator /(const Complex &x,const Complex &y){
	return (Complex){(x.real*y.real+x.imag*y.imag)/(y.real*y.real+y.imag*y.imag),(x.imag*y.real-x.real*y.imag)/(y.real*y.real+y.imag*y.imag)}; 
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=0;i<=n;i++){
		scanf("%lf",&f[i].real); 
	}
	for(int i=0;i<=m;i++){
		scanf("%lf",&f[i].imag);
	}
	while(len<=n+m){
		len*=2;
		deg++;
	}
	for(int i=0;i<len;i++){
		int rev=0; 
		for(int j=0;j<deg;j++){
			if(i&(1<<j)){
				rev+=1<<(deg-1-j);
			}
		}
		if(i<rev){
			swap(f[i],f[rev]);
		}
	}
	for(int i=0;i<deg;i++){
		for(int l1=0;l1<len;l1+=1<<(i+1)){
			Complex omega=(Complex){cos(pi/(1<<i)),sin(pi/(1<<i))},pre=(Complex{1,0}); 
			int l2=l1+(1<<i);
			for(int j=0;j<(1<<i);j++){
				buf1=f[l1+j]+(~pre)*f[l2+j];
				buf2=f[l1+j]+(~(-pre))*f[l2+j];
				f[l1+j]=buf1;
				f[l2+j]=buf2;
				pre=pre*omega; 
			}
		}
	}
	for(int i=0;i<len;i++){
		f[i]=f[i]*f[i];
	}
	for(int i=0;i<len;i++){
		int rev=0; 
		for(int j=0;j<deg;j++){
			if(i&(1<<j)){
				rev+=1<<(deg-1-j);
			}
		}
		if(i<rev){
			swap(f[i],f[rev]);
		}
	}
	for(int i=0;i<deg;i++){
		for(int l1=0;l1<len;l1+=1<<(i+1)){
			Complex omega=(Complex){cos(pi/(1<<i)),-sin(pi/(1<<i))},pre=(Complex{1,0}); 
			int l2=l1+(1<<i);
			for(int j=0;j<(1<<i);j++){
				buf1=f[l1+j]+(~pre)*f[l2+j];
				buf2=f[l1+j]+(~(-pre))*f[l2+j];
				f[l1+j]=buf1;
				f[l2+j]=buf2;
				pre=pre*omega; 
			}
		}
	}
	for(int i=0;i<=n+m;i++){
		printf("%lld ",(long long)(f[i].imag/len/2+0.5));
	}
	return 0;
}

评测结果