代码

#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];
	int R[N];
	void DFT(cp* a, int n) {
		for (int i=0; i<n; ++i)
			if (i < R[i]) swap(a[i], a[R[i]]);
		for (int i = 1, t = n >> 1; i < n; i <<= 1, t >>= 1) {
			for (int j = 0, p = (i << 1); j < n; j += p) {
				cp *x = a + j, *y = a + j + i, *w = W;
				for (int k = 0; k < i; ++k, ++x, ++y, w += t) {
					cp tmp = *w **y;
					*y = *x - tmp, *x = *x + tmp;
				}
			}
		}
	}
	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) A[i].y=_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);
		For(i,0,n-1) A[i]=A[i]*A[i];
		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);
		For(i,0,n-1) _A[i]=A[i].y/n/2+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;
}

评测结果