代码

#include<bits/stdc++.h>
using namespace std; 
const int N=21e5+3;
const double P=acos(-1);
struct C{
	double x,y;
	C operator+(C a)const{return{x+a.x,y+a.y};}
	C operator-(C a)const{return{x-a.x,y-a.y};}
	C operator*(C a)const{return{x*a.x-y*a.y,x*a.y+y*a.x};}
}a[N],b[N],w[N];
int n,r[N];
void pre(int m){
	int i,j;
	for(n=1;n<=m;n<<=1);
	for(i=0,w[j=n>>1]={1,0};i<n;++i)r[i]=(r[i>>1]>>1)|((i&1)?j:0);
	C g={cos(2*P/n),sin(2*P/n)};
	for(i=j+1;i<n;++i)w[i]=w[i-1]*g;
	for(i=j-1;i>0;--i)w[i]=w[i<<1];
}
void fft(C*a,bool b=0){
	int i,j,k;
	C *g,*u,*v,x;
	for(i=0;i<n;++i)if(i<r[i])swap(a[i],a[r[i]]);
	for(i=1;i<n;i<<=1)for(j=0;j<n;j+=i<<1)for(k=0,g=w+i,u=a+j,v=u+i;k<i;++k)
	x=g[k]*v[k],v[k]=u[k]-x,u[k]=u[k]+x;
	if(b)for(i=0,reverse(a+1,a+n);i<n;++i)a[i].x/=n,a[i].y/=n;
}
int main(){
	int m,i;
	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);
	pre(m+=n),fft(a),fft(b);
	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+0.5));
	return 0;
}

评测结果