代码

#include<cstdio>
#include<cmath>
const double PI=acos(-1);
const int N=262151;
struct C{
	double x,y;
	inline C operator+(C a)const{return{x+a.x,y+a.y};}
	inline C operator-(C a)const{return{x-a.x,y-a.y};}
	inline C operator*(C a)const{return{x*a.x-y*a.y,x*a.y+y*a.x};}
}a[N],b[N];
int n,r[N];
void fft(C*a,int b){
	C u,v,x,y;
	int i,j,k,l,p;
	for(i=0;i<n;++i)if(i<r[i])u=a[i],a[i]=a[r[i]],a[r[i]]=u;
	for(i=1;i<n;i<<=1)
	for(u={cos(PI/i),sin(PI/i)*b},j=0,l=i<<1;j<n;j+=l)
	for(v={1,0},k=j,p=j+i;k<p;++k,v=v*u)
	x=a[k],y=v*a[i+k],a[k]=x+y,a[i+k]=x-y;
}
int main(){
	int m,i,l=-1;
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;++i)scanf("%lf",&a[i].x);
	for(i=0;i<=m;++i)scanf("%lf",&b[i].x);
	for(m+=n,n=1;n<=m;n<<=1)++l;
	for(i=0;i<n;++i)r[i]=(r[i>>1]>>1)|((i&1)<<l);
	fft(a,1),fft(b,1);
	for(i=0;i<n;++i)a[i]=a[i]*b[i];
	fft(a,-1);
	for(i=0;i<=m;++i)printf("%d ",int(a[i].x/n+0.5));
	return 0;
}

评测结果