代码

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

typedef unsigned long long ull;

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

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 W[N], r[N], pw[N];
ull tmp[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]]);
	}
	for (int i = 0; i < n; ++ i) tmp[i] = a[i];
	for (int h = 2; h <= n; h <<= 1) {
		pw[0] = 1;
		for (int i = 0; i < h; ++ i)
			pw[i + 1] = 1LL * pw[i] * W[h] % mod;
		for (int i = 0; i < n; i += h) {
			int *w = pw;
			ull *u = tmp + i, *v = tmp + i + h / 2;
			int j;
			#define S {                      \
				ull x = *v * *w % mod;         \
				*v = *u + mod - x; *u += x;    \
				++ u; ++ v; ++ w; ++ j; }
			for (j = i; j + 8 <= i + h / 2; ) {
				S S S S S S S S
			}
			for (; j < i + h / 2; ) S
		}
	}
	for (int i = 0; i < n; ++ i) a[i] = tmp[i] % mod;
	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] = qp(g, (mod - 1) / i);
	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;
}

评测结果