代码

#include <cmath>
#include <cstdio>
#include <algorithm>

typedef unsigned long long ull;
const size_t maxL = 1 << 18 | 1;
const double pi = std::acos(-1.0);

struct complex_t
{
	double a, b; //a + bi
	complex_t(double _a = 0.0, double _b = 0.0) : a(_a), b(_b) {}
} A[maxL], B[maxL];;
inline complex_t operator+(const complex_t &a, const complex_t &b)
{
	return complex_t(a.a + b.a, a.b + b.b);
}
inline complex_t operator-(const complex_t &a, const complex_t &b)
{
	return complex_t(a.a - b.a, a.b - b.b);
}
inline complex_t operator*(const complex_t &a, const complex_t &b)
{
	return complex_t(a.a * b.a - a.b * b.b, a.a * b.b + a.b * b.a);
}

int N, M;
int Rev[maxL];

void DFT_pre(int l, int bitcnt)
{
	for (int i = 1; i != l; ++i)
		Rev[i] = (Rev[i >> 1] >> 1) | ((i & 1) << bitcnt - 1);
}

void DFT(complex_t *a, int n)
{
	for (int i = 1; i != n; ++i)
		if (i < Rev[i])
			std::swap(a[i], a[Rev[i]]);
	for (int l = 1; l != n; l <<= 1)
	{
		complex_t w0(std::cos(pi / l), std::sin(pi / l));
		static complex_t wn[maxL];
		wn[0] = 1.0;
		for (int i = 1; i != l; ++i)
			wn[i] = wn[i - 1] * w0;
		for (int i = 0; i != n; i += l * 2)
			for (int j = 0; j != l; ++j)
			{
				auto x = a[i + j], y = wn[j] * a[i + l + j];
				a[i + j] = x + y;
				a[i + l + j] = x - y;
			}
	}
}

void iDFT(complex_t *a, int n)
{
	for (int i = 1; i != n; ++i)
		if (i < Rev[i])
			std::swap(a[i], a[Rev[i]]);
	for (int l = 1; l != n; l <<= 1)
	{
		complex_t w0(std::cos(pi / l), -std::sin(pi / l));
		static complex_t wn[maxL];
		wn[0] = 1.0;
		for (int i = 1; i != l; ++i)
			wn[i] = wn[i - 1] * w0;
		for (int i = 0; i != n; i += l * 2)
			for (int j = 0; j != l; ++j)
			{
				auto x = a[i + j], y = wn[j] * a[i + l + j];
				a[i + j] = x + y;
				a[i + l + j] = x - y;
			}
	}
	for (int i = 0; i != n; ++i)
		a[i].a /= n;
}

int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 0, x; i <= N; ++i)
	{
		scanf("%d", &x);
		A[i].a = x;
	}
	for (int i = 0, x; i <= M; ++i)
	{
		scanf("%d", &x);
		B[i].a = x;
	}
	
	int l = 1, bitcnt = 0;
	
	while (l <= N + M)
		l <<= 1, ++bitcnt;
	
	DFT_pre(l, bitcnt);
	DFT(A, l);
	DFT(B, l);
	
	for (int i = 0; i != l; ++i)
		A[i] = A[i] * B[i];
	
	iDFT(A, l);
	
	for (int i = 0; i <= N + M; ++i)
		printf("%d%c", (int)(A[i].a + 0.5), " \n"[i == N + M]);

	return 0;
}

评测结果