代码

#include <bits/stdc++.h>
using namespace std;

const double pi (acos(-1));
const int MaxN(500003);
int rev[MaxN];

struct comp_t
{
	double x, y;
	comp_t(double _x = 0, double _y = 0) : x(_x), y(_y) { }
	inline comp_t operator + (const comp_t &T)
	{ return comp_t(x + T.x, y + T.y); }
	inline comp_t operator - (const comp_t &T)
	{ return comp_t(x - T.x, y - T.y); }
	inline comp_t operator * (const comp_t &T)
	{ return comp_t(x * T.x - y * T.y, x * T.y + y * T.x); }
	inline comp_t conj()
	{ return comp_t(x, -y); }
}A[MaxN], B[MaxN], F[MaxN];

void dft(comp_t *a, int n, int f)
{
	for(int i = 1; i < n; i++)
		if(i < rev[i])
			swap(a[i], a[rev[i]]);
	for(int l = 1; l < n; l <<= 1)
	{
		comp_t wn(cos(pi / l), sin(pi / l) * f);
		static comp_t w[MaxN];
		w[0] = 1.0;
		for(int i = 1; i < l; i++)
			w[i] = w[i - 1] * wn;
		for(int i = 0; i < n; i += l << 1)
			for(int j = 0; j < l; j++)
			{
				comp_t x = a[i + j], y = a[i + j + l] * w[j];
				a[i + j] = x + y, a[i + j + l] = x - y;
			}
	}
	if(f == -1)
		for(int i = 0; i < n; i++)
			a[i].x /= n;
}

int main()
{
	int n, m, L, k;
	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);
	for(L = 1, k = -1; L < n + m; L <<= 1, ++k);
	for(int i = 1; i < L; i++)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << k);
	for(int i = 0; i < L; i++)
		F[i] = comp_t(A[i].x, B[i].x);
	dft(F, L, 1);
	for(int i = 0; i < L; i++)
	{
		int j = (L - i) & (L - 1);
		A[i] = ((F[i] + F[j].conj()) * comp_t(0.5, 0)) * ((F[i] - F[j].conj()) * comp_t(0, -0.5));
	}
	dft(A, L, -1);
	for(int i = 0; i < n + m - 1; i++)
		printf("%d%c", (int) floor(A[i].x + 0.5), " \n" [i == n + m - 2]);
	return 0;
}

评测结果