代码

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353, g = 3;
const int N = 1 << 18;

int qp(int x, int n) {
	int ans = 1;
	for (; n; n >>= 1, x = 1LL * x * x % mod)
		n & 1 && (ans = 1LL * ans * x % mod);
	return ans;
}
int inv(int x) {return qp(x, mod - 2);}

int add(int x, int y) {return x + y < mod ? x + y : x + y - mod;}
int sub(int x, int y) {return x - y >= 0 ? x - y : x - y + mod;}

int W[N], r[N];

void ntt(int *a, int n, int f) {
	int k = __builtin_ctz(n);
	for (int i = 1; i < n - 1; ++ i) {
		r[i] = r[i >> 1] >> 1 | (i & 1) << k - 1;
		if (i < r[i]) swap(a[i], a[r[i]]);
	}
	if (n >= 2) {
		for (int i = 0, v; i < n; i += 2) {
			v = a[i + 1];
			a[i + 1] = sub(a[i], v), a[i] = add(a[i], v);
		}
	}
	if (n >= 4) {
		for (int i = 0, v; i < n; i += 4) {
			v = 1LL * a[i + 2] * W[2] % mod;
			a[i + 2] = sub(a[i], v); a[i] = add(a[i], v);
			v = 1LL * a[i + 3] * W[3] % mod;
			a[i + 3] = sub(a[i + 1], v), a[i + 1] = add(a[i + 1], v);
		}
	}
	for (int h = 4; h < n; h <<= 1) {
		for (int i = 0; i < n; i += h << 1) {
			int *w = W + h, *ed = W + (h << 1), *u = a + i, *v = a + i + h, x;
			#define S(u, v, w)               \
				x = 1LL * *(v) * *(w) % mod; \
				*(v) = sub(*(u), x);         \
				*(u) = add(*(u), x);
			while (w < ed) {
				S(u + 0, v + 0, w + 0)
				S(u + 1, v + 1, w + 1)
				S(u + 2, v + 2, w + 2)
				S(u + 3, v + 3, w + 3)
				u += 4, v += 4, w += 4;
			}
		}
	}
	if (!~f) {
		reverse(a + 1, a + n); int Inv = inv(n);
		for (int i = 0; i < n; ++ i) a[i] = 1LL * a[i] * Inv % mod;
	}
}

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	int siz = 1; while (siz < n + m + 1) siz <<= 1;
	for (int i = 1; i < siz; i <<= 1) {
		W[i] = 1; int wn = qp(g, (mod - 1) / (i << 1));
		for (int j = 1; j < i; ++ j)
			W[i + j] = 1LL * W[i + j - 1] * wn % mod;
	}
	int *a = new int[siz];
	for (int i = 0; i <= n; ++ i) scanf("%d", &a[i]);
	for (int i = n + 1; i < siz; ++ i) a[i] = 0;
	int *b = new int[siz];
	for (int i = 0; i <= m; ++ i) scanf("%d", &b[i]);
	for (int i = m + 1; i < siz; ++ i) b[i] = 0;
	ntt(a, siz, 1); ntt(b, siz, 1);
	int *c = new int[siz];
	for (int i = 0; i < siz; ++ i) c[i] = 1LL * a[i] * b[i] % mod;
	ntt(c, siz, -1);
	for (int i = 0; i <= n + m; ++ i) printf("%d ", c[i]); puts("");
	return 0;
}

评测结果