代码

#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 operator /= (const double &T)
	{
		x /= T, y /= T;
		return *this;
	}
	inline comp_t conj()
	{ return comp_t(x, -y); }
}A[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;
			}
	}
}

int main()
{
	int n, m, L, k;
	scanf("%d%d", &n, &m);
	for(int i = 0; i <= n; i++)
		scanf("%lf", &A[i].x);
	for(int i = 0; i <= m; i++)
		scanf("%lf", &A[i].y);
	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);
	dft(A, L, 1);
	A[L] = A[0];
	for(int i = 0; i <= L - i; i++)
	{
		comp_t t1 = (A[i] + A[L - i].conj()) * comp_t(0, 1) * (A[i] - A[L - i].conj());
		comp_t t2 = (A[L - i] + A[i].conj()) * comp_t(0, 1) * (A[L - i] - A[i].conj());
		t1 /= 4, t2 /= 4;
		A[i] = t1, A[L - i] = t2;
	}
	dft(A, L, -1);
	for(int i = 0; i <= n + m; i++)
		printf("%d ", (int) (-A[i].x / L + 0.5));
	return 0;
}

评测结果