代码

#include <bits/stdc++.h>

#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl

using namespace std;

using VI = vector<int>;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

template<typename T = int>
inline T read() {
	T x(0), sgn(1); char ch(getchar());
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
	return x * sgn;
}

struct Complex {
	double re, im;
	inline Complex friend operator + (const Complex &lhs, const Complex &rhs) {
		return (Complex) {lhs.re + rhs.re, lhs.im + rhs.im};
	}
	inline Complex friend operator - (const Complex &lhs, const Complex &rhs) {
		return (Complex) {lhs.re - rhs.re, lhs.im - rhs.im};
	}
	inline Complex friend operator * (const Complex &lhs, const Complex &rhs) {
		return (Complex) {lhs.re * rhs.re - lhs.im * rhs.im, lhs.re * rhs.im + lhs.im * rhs.re};
	}
};

const double Pi = acos(-1.0);

template<int Maxn>
struct Poly {

	int rev[Maxn], len;

	void FFT(Complex *P, int opt) {
		Rep (i, len) if (i < rev[i]) swap(P[i], P[rev[i]]);
		for (int i = 2, p = 1; i <= len; p = i, i <<= 1) {
			Complex Wi = (Complex) {cos(2 * Pi / i), opt * sin(2 * Pi / i)};
			for (int j = 0; j < len; j += i) {
				Complex x = (Complex) {1, 0};
				Rep (k, p) {
					Complex u = P[j + k], v = x * P[j + k + p];
					P[j + k] = u + v; P[j + k + p] = u - v;
					x = x * Wi;
				}
			}
		}
		if (!~opt) Rep (i, len) P[i].re /= len;
	}

	Complex A[Maxn], B[Maxn], C[Maxn];

	void Mult(const VI &a, const VI &b, VI &c) {
		int na = a.size() - 1, nb = b.size() - 1, nc = na + nb, cnt = 0;

		for (len = 1; len <= nc; len <<= 1) ++ cnt;
		Rep (i, len) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (cnt - 1));

		Rep (i, len) A[i] = (Complex) {i <= na ? 1.0 * a[i] : 0, 0};
		Rep (i, len) B[i] = (Complex) {i <= nb ? 1.0 * b[i] : 0, 0};

		FFT(A, 1); FFT(B, 1);
		Rep (i, len) C[i] = A[i] * B[i];
		FFT(C, -1);

		c.clear(); c.resize(nc + 1);

		Rep (i, len) c[i] = int(C[i].re + 0.5);
	}

};

void File() {
#ifndef ONLINE_JUDGE
	freopen ("fft.in", "r", stdin);
	freopen ("fft.out", "w", stdout);
#endif
}

Poly<1 << 21> T;

VI a, b, c;

int main() {

	File();

	a.resize(read() + 1);
	b.resize(read() + 1);
	Rep (i, a.size()) a[i] = read();
	Rep (i, b.size()) b[i] = read();

	T.Mult(a, b, c);
	Rep (i, c.size())
		printf ("%d%c", c[i], i == c.size() - 1 ? '\n' : ' ');

	return 0;

}

评测结果