代码

#include<bits/stdc++.h>
#define x first
#define y second
#pragma GCC optimize(3)
#define FOR(a,b,c) for(int a=(b),a##_end=(c);a<=a##_end;++a)
#define ROF(a,b,c) for(int a=(b),a##_end=(c);a>=a##_end;--a)
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<int,int> PII;
const db Pi=acos(-1);
const int INF=0x3f3f3f3f,N=3e5+10;
template<class T>inline bool chkmin(T &A,T B){return B<A?A=B,1:0;}
template<class T>inline bool chkmax(T &A,T B){return A<B?A=B,1:0;}
namespace FFT{
	struct Cp{
		db x,y;
		inline Cp operator + (const Cp &B)const{return {x+B.x,y+B.y};}
		inline Cp operator - (const Cp &B)const{return {x-B.x,y-B.y};}
		inline Cp operator * (const Cp &B)const{return {x*B.x-y*B.y,x*B.y+y*B.x};}
	}a[N],b[N],c[N],d[N],w[N];
	int rev[N];
	void DFT(Cp *A,int n){
		FOR(i,0,n-1)if(i<rev[i])swap(A[i],A[rev[i]]);
		w[0]={1,0};
		for(int i=1;i<n;i<<=1){
			Cp wn{cos(Pi/i),sin(Pi/i)};
			for(int j=i-2;j>=0;j-=2)w[j+1]=wn*(w[j]=w[j>>1]);
			for(int j=0;j<n;j+=i<<1){
				Cp *p=A+j,*q=A+j+i;
				FOR(k,0,i-1){
					Cp x=p[k],y=q[k]*w[k];
					p[k]=x+y,q[k]=x-y;
				}
			}
		}
	}
	void Solve(int *A,int *B,int *C,int m1,int m2){
		FOR(i,0,m1-1)a[i]={A[i]&32767,A[i]>>15};
		FOR(i,0,m2-1)b[i]={B[i]&32767,B[i]>>15};
		int L=0,n=1;
		for(;n<m1+m2;n<<=1,++L);
		FOR(i,0,n-1)rev[i]=rev[i>>1]>>1|(i&1)<<(L-1);
		DFT(a,n);DFT(b,n);
		FOR(i,0,n-1){
			int j=(n-1)&(n-i);
			c[j]=(Cp){0.5*(a[i].x+a[j].x),0.5*(a[i].y-a[j].y)}*b[i];
			d[j]=(Cp){0.5*(a[i].y+a[j].y),0.5*(a[j].x-a[i].x)}*b[i];
		}
		DFT(c,n);DFT(d,n);
		FOR(i,0,m1+m2-2){
			ll u=c[i].x/n+0.5,v=c[i].y/n+0.5;
			ll x=d[i].x/n+0.5,y=d[i].y/n+0.5;
			C[i]=u+((v+x)<<15)+(y<<30);
		}
		FOR(i,0,n-1)a[i]=b[i]=c[i]=d[i]={0,0};
	}
}
int n,m,A[N],B[N],C[N];
int main(){
	scanf("%d%d",&n,&m);
	FOR(i,0,n)scanf("%d",&A[i]);
	FOR(i,0,m)scanf("%d",&B[i]);
	FFT::Solve(A,B,C,n+1,m+1);
	FOR(i,0,n+m)printf("%d ",C[i]);
	putchar('\n');
	return 0;
}

评测结果