代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1 << 18;

const int P = 998244353, R = 3;

typedef long long ll;

int a[N], b[N];

void ntt(int* arr, int lgn, bool inv);
int mpow(int a, int k);
void exGcd(int a, int b, int& x, int& y);
int rev(int a, int p = P);

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n; ++i)
		scanf("%d", &a[i]);
	for (int i = 0; i <= m; ++i)
		scanf("%d", &b[i]);
	int l = n + m, lgl = 0;
	while ((1 << lgl) <= l)
		++lgl;
	ntt(a, lgl, false);
	ntt(b, lgl, false);
	for (int i = 0; i < (1 << lgl); ++i)
		a[i] = a[i] * (ll)b[i] % P;
	ntt(a, lgl, true);
	for (int i = 0; i <= l; ++i)
		printf("%d ", a[i]);
	return 0;
}

int mpow(int a, int k) {
	int ret = 1;
	while (k) {
		if (k & 1)
			ret = (ll)ret * a % P;
		a = a * (ll)a % P;
		k >>= 1;
	}
	return ret;
}

void exGcd(int a, int b, int& x, int& y) {
	if (!b) {
		x = 1;
		y = 0;
		return;
	}
	exGcd(b, a % b, y, x);
	y -= a / b * x;
}

int rev(int a, int p) {
	int x, y;
	exGcd(a, p, x, y);
	if (x < 0)
		x += p;
	return x;
}

void ntt(int* arr, int lgn, bool inv) {
	static int rev[N];
	int n = 1 << lgn;
	for (int i = 1; i < n; ++i)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lgn - 1));
	for (int i = 0; i < n; ++i)
		if (i < rev[i])
			swap(arr[i], arr[rev[i]]);
	int rt = inv ? ::rev(R) : R;
	for (int i = 0; i < lgn; ++i) {
		int t = 1 << i, g = mpow(rt, (P - 1) >> (i + 1));
		for (int j = 0; j < n; j += t << 1) {
			int w = 1;
			for (int k = j; k < j + t; ++k) {
				int a0 = arr[k], a1 = arr[k + t];
				arr[k] = (a0 + a1 * (ll)w) % P;
				arr[k + t] = (a0 + a1 * (ll)(P - w)) % P;
				w = w * (ll)g % P;
			}
		}
	}
	if (inv) {
		int rm = ::rev(n);
		for (int i = 0; i < n; ++i)
			arr[i] = arr[i] * (ll)rm % P;
	}
}

评测结果