代码

#include <bits/stdc++.h>

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fm, to)    for (int i = fm; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;
typedef unsigned long long u64;

using namespace std;

const int nsz = 1e6, ort = 3, mod = 998244353;
int rev[nsz + 5];

int inline add(int a, int b) {
	return (a + b >= mod) ? a + b - mod : a + b;
}

int inline sub(int a, int b) {
	return (a - b < 0) ? a - b + mod : a - b;
}

int inline mul(int a, int b) {
	return (num) a * b % mod;
}

int inline qpow(int a, int p) {
	int res = 1;
	for (; p; p >>= 1) {
		p & 1 && (res = mul(res, a));
		a = mul(a, a);
	}
	return res;
}

int inline inv(int a) {
	return qpow(a, mod - 2);
}

typedef vector<int> poly;

void inline fix(poly &a) {
	for (; a.size() && !a.back(); a.pop_back());
}

poly inline operator + (int a, poly b) {
	poly res = b;
	res[0] = add(res[0], a);
	return res;
}

poly operator + (poly a, poly b) {
	poly res(max(a.size(), b.size()));
	loop (i, res.size()) {
		res[i] = add(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
	}
	return res;
}

poly operator - (poly a, poly b) {
	poly res(max(a.size(), b.size()));
	loop (i, res.size()) {
		res[i] = sub(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
	}
	return res;
}

poly inline operator * (int a, poly b) {
	loop (i, b.size()) {
		b[i] = mul(b[i], a);
	}
	return b;
}

void inline dft(poly &a, int tp = 1) {
	int k = 0;
	static u64 b[nsz + 5], pw[nsz + 5];
	for (int tmp = (int) a.size() - 1; tmp; tmp >>= 1, ++k);
	loop (i, a.size()) {
		b[i] = a[i];
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
		if (i > rev[i]) {
			swap(b[i], b[rev[i]]);
		}
	}
	for (int k = 1; k < a.size(); k <<= 1) {
		int w0 = qpow(ort, (mod - 1) / (k << 1));
		tp == -1 && (w0 = qpow(w0, mod - 2));
		pw[0] = 1;
		circ (i, 1, k - 1) {
			pw[i] = pw[i - 1] * w0 % mod;
		}
		for (int l = 0; l < a.size(); l += (k << 1)) {
			u64 *p0 = b + l, *p1 = b + l + k, *w = pw, d;
			for (int i = 0; i < k; ++i, ++w, ++p0, ++p1) {
				d = *w * *p1 % mod;
				*p1 = *p0 - d + mod;
				*p0 += d;
			}
		}
	}
	loop (i, a.size()) {
		a[i] = b[i] % mod;
	}
	if (tp == 1)  return;
	a = inv(a.size()) * a;
}

poly inline operator * (poly a, poly b) {
	int len = 1, n = (int) a.size() - 1, m = (int) b.size() - 1;
	for (; len <= n + m; len <<= 1);
	a.resize(len), b.resize(len);
	dft(a), dft(b);
	loop (i, len) {
		a[i] = mul(a[i], b[i]);
	}
	dft(a, -1);
	a.resize(n + m + 1);
	return a;
}

poly inv(poly a) {
	if (a.size() == 1)  return vector<int>(1, inv(a[0]));
	int to = (a.size() + 1) >> 1;
	poly res(a.size()), pa(to);
	loop (i, to) {
		pa[i] = a[i];
	}
	res = inv(pa);
	res = 2 * res - a * res * res;
	res.resize(a.size());
	return res;
}

int n, m;
poly f, g, h;

int main() {
	scanf("%d%d", &n, &m);
	f.resize(n + 1), g.resize(m + 1);
	circ (i, 0, n) {
		scanf("%d", &f[i]);
	}
	circ (i, 0, m) {
		scanf("%d", &g[i]);
	}
	h = f * g;
	loop (i, h.size()) {
		printf("%d ", h[i]);
	}
	printf("\n");
}

评测结果