代码

// luogu-judger-enable-o2
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;

int n,m;
struct complex{
	double x,y;
	complex operator+(complex a)const {return (complex){x+a.x,y+a.y};}
	complex operator-(complex a)const {return (complex){x-a.x,y-a.y};}
	complex operator*(complex a)const {return (complex){x*a.x-y*a.y,x*a.y+y*a.x};}
}a[3000010],b[3000010];
int lim=1,l=0;
int where[3000010];
double co[3000010],si[3000010];
const double Pi=acos(-1.0)*2.0;
complex wn,w,fa,fb;

void dft(complex *now,int idft){
	for(int i=0;i<lim;i++) if(where[i]>i) swap(now[i],now[where[i]]);
	complex wn,w,a,b;
	for(int l=2;l<=lim;l*=2){
		wn=(complex){cos(Pi/l),idft*sin(Pi/l)};
		for(int i=0;i<lim;i+=l){
			w=(complex){1,0};
			for(int x=i,y=i+l/2;y<i+l;x++,y++,w=w*wn){
				a=now[x],b=now[y]*w;
				now[x]=a+b;
				now[y]=a-b;
			}
		}
	}
}

int main(){
	scanf("%d %d",&n,&m);n++;m++;
	for(int i=0;i<n;i++) scanf("%lf",&a[i].x);
	for(int i=0;i<m;i++) scanf("%lf",&b[i].x);
	while(lim<n+m-1) lim*=2,l++,co[lim]=cos(Pi/lim),si[lim]=sin(Pi/lim);
	for(int i=0;i<lim;i++) where[i]=((where[i>>1]>>1) | ((i&1)<<(l-1)));
	dft(a,1);dft(b,1);
	for(int i=0;i<lim;i++) a[i]=a[i]*b[i];
	dft(a,-1);
	for(int i=0;i<n+m-1;i++) printf("%d ",(int)(a[i].x/lim+0.5));
}

评测结果