代码

#include <bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;++a)
using namespace std;
namespace FFT {
	const int N=270000;
	const double pi=acos(-1);
	struct cp {
		double x,y;
		cp operator + (const cp &_) {return (cp){x+_.x,y+_.y};}
		cp operator - (const cp &_) {return (cp){x-_.x,y-_.y};}
		cp operator * (const cp &_) {return (cp){x*_.x-y*_.y,x*_.y+y*_.x};}
	}A[N],B[N],W[N],y;
	int R[N];
	void DFT (cp *A,int n,int o) {
		For(i,0,n-1) if (i<R[i]) swap(A[i],A[R[i]]);
		for(int i=2;i<=n;i<<=1) {
			for(int j=0;j<n;j+=i) {
				For(k,0,(i>>1)-1) {
					y=W[n/i*k]*A[j+k+(i>>1)];
					A[j+k+(i>>1)]=A[j+k]-y;
					A[j+k]=A[j+k]+y;
				}
			}
		}
		if (o<0) For(i,0,n-1) A[i].x/=n;
	}
	void Mul (int *_A,int a,int *_B,int b) {
		int n=(1<<(int)log2(a+b)<<1);
		For(i,0,n-1) R[i]=(R[i>>1]>>1)|((i&1)*(n>>1));
		For(i,0,a-1) A[i].x=_A[i];
		For(i,0,b-1) B[i].x=_B[i];
		cp t=(cp){cos(2*pi/n),sin(2*pi/n)};
		W[0]=(cp){1,0}; For(i,1,n-1) W[i]=W[i-1]*t;
		DFT(A,n,1),DFT(B,n,1);
		t=(cp){cos(2*pi/n),-sin(2*pi/n)};
		W[0]=(cp){1,0}; For(i,1,n-1) W[i]=W[i-1]*t;
		For(i,0,n-1) A[i]=A[i]*B[i];
		DFT(A,n,-1);
		For(i,0,n-1) _A[i]=A[i].x+0.5;
	}
}
using FFT::Mul;

const int N=100007;
int A[N],B[N],a,b;
int main () {
	scanf("%d%d",&a,&b),++a,++b;
	For(i,0,a-1) scanf("%d",&A[i]);
	For(i,0,b-1) scanf("%d",&B[i]);
	Mul(A,a,B,b);
	For(i,0,a+b-2) printf("%d ",A[i]);
	return 0;
}

评测结果