代码

#include <algorithm>

using LL = long long;

const int mod = 998244353;
const int N = 1 << 21;

int rev[N], wn[N + 1], lim, s;

int pow(int x, int y) {
	int ans = 1;
	for (; y; y >>= 1, x = static_cast<LL> (x) * x % mod)
		if (y & 1) ans = static_cast<LL> (ans) * x % mod;
	return ans;
}

void fftinit(int len) {
	lim = 1, s = -1;
	while (lim < len)
		lim <<= 1, s++;
	for (int i = 0; i < lim; i++)
		rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
	wn[0] = 1;
	const int g = pow(3, (mod - 1) / lim);
	for (int i = 1; i <= lim; i++)
		wn[i] = static_cast<LL> (wn[i - 1]) * g % mod;
}

void reduce(int &x) {
	x += x >> 31 & mod;
}

void fft(int *A, int typ) {
	for (int i = 0; i < lim; i++)
		if (i < rev[i])
			std::swap(A[i], A[rev[i]]);
	for (int i = 1; i < lim; i <<= 1) {
		const int t = lim / i / 2;
		for (int j = 0; j < lim; j += i << 1)
			for (int k = 0; k < i; k++) {
				const int x = A[k + j], y = static_cast<LL> (A[k + j + i]) * wn[typ ? t * k : lim - t * k] % mod;
				reduce(A[k + j] += y - mod), reduce(A[k + j + i] = x - y);
			}
	}
	if (!typ) {
		const int ilim = pow(lim, mod - 2);
		for (int i = 0; i < lim; i++)
			A[i] = static_cast<LL> (A[i]) * ilim % mod;
	}
}

int tA[N], tB[N];

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
	fftinit(n + m + 1);
	std::copy(a, a + n + 1, tA), std::copy(b, b + m + 1, tB);
	fft(tA, 1), fft(tB, 1);
	for (int i = 0; i < lim; i++)
		tA[i] = static_cast<LL> (tA[i]) * tB[i] % mod;
	fft(tA, 0);
	std::copy(tA, tA + n + m + 1, c);
}

评测结果