代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cmath>
inline int read() {
	register int ret, cc;
	while (!isdigit(cc = getchar())){}ret = cc-48;
	while ( isdigit(cc = getchar()))  ret = cc-48+ret*10;
	return ret;
}
const int MAXN = 500010;

struct Complex {
	double x, y;
	Complex(double x = 0, double y = 0):x(x), y(y) { }
	inline Complex operator + (const Complex& rhs) const { return Complex(x + rhs.x, y + rhs.y); }
	inline Complex operator - (const Complex& rhs) const { return Complex(x - rhs.x, y - rhs.y); }
	inline Complex operator * (const Complex& rhs) const { return Complex(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
};
const double pi = acos(-1);
int rev[MAXN];
int getrev(int n) {
	int bln = 1, bct = 0;
	while (bln < n) bln <<= 1, bct++;
	for (int i = 0; i < bln; ++i)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bct - 1));
	return bln;
}

void FFT(Complex* a, int n, int opt) {
	for (int i = 0; i < n; ++i) if (i < rev[i])
		std::swap(a[i], a[rev[i]]);
	for (int i = 1; i < n; i <<= 1) {
		Complex wn(cos(pi / i), opt * sin(pi / i));
		for (int j = 0, p = i << 1; j < n; j += p) {
			Complex w = 1;
			for (int k = 0; k < i; ++k, w = w * wn) {
				Complex x = a[j + k], y = w * a[j + k + i];
				a[j + k] = x + y;
				a[j + k + i] = x - y;
			}
		}
	}
	if (opt == -1) for (int i = 0; i < n; ++i) a[i].x /= n, a[i].y /= n;
}
Complex A[MAXN], B[MAXN];
int main() {
#ifdef ARK
	freopen("test.in", "r", stdin);
#endif
	int N = read() + 1, M = read() + 1;
	for (int i = 0; i < N; ++i) A[i] = read();
	for (int i = 0; i < M; ++i) B[i] = read();
	int len = N + M - 1;
	int bln = getrev(len);
	FFT(A, bln, 1), FFT(B, bln, 1);
	for (int i = 0; i < bln; ++i) A[i] = A[i] * B[i];
	FFT(A, bln, -1);
	for (int i = 0; i < len; ++i) printf("%d ", (int)(A[i].x + 0.5));
	puts("");
}

评测结果