代码

#include<bits/stdc++.h>
using namespace std;
const int N=6e5+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];
int n,r[N];
void fft(C*a,int b=1){
	int i,j,k;
	C o,w,*u,*v,x;
	for(i=0;i<n;++i)if(i<r[i])x=a[i],a[i]=a[r[i]],a[r[i]]=x;
	for(i=1;i<n;i<<=1)for(o={cos(P/i),sin(P/i)*b},j=0;j<n;j+=i<<1)for(k=0,w={1,0},u=a+j,v=u+i;k<i;++k,w=w*o)
	x=w*v[k],v[k]=u[k]-x,u[k]=u[k]+x;
}
char c1[N],*k1=c1,*k2;
void in(int&x){
	for(x=0;*k1>'9'||*k1<'0';++k1);
	for(;*k1<='9'&&*k1>='0';x=x*10+((*k1++)-48));
}
char c2[N],st[9],*k3=c2,*k4;
void out(int x){
	if(!x){
		*k3++=48,*k3++=' ';
		return;
	}
	for(k4=st+1,*k4=' ';x;*++k4=x%10+48,x/=10);
	for(;k4!=st;*k3++=*k4--);
}
int main(){
	fread(c1,1,N-2,stdin);
	int m,i,j;
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;++i)in(j),a[i].x=j;
	for(i=0;i<=m;++i)in(j),b[i].x=j;
	for(m+=n,n=1;n<=m;n<<=1);
	for(i=0,j=n>>1;i<n;++i)r[i]=(r[i>>1]>>1)|((i&1)?j:0);
	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)out(int(a[i].x/n+0.5));
	fwrite(c2,1,k3-c2,stdout);
	return 0;
}

评测结果