代码

#include <bits/stdc++.h>

template <class T>
using V = std::vector<T>;
using ll = long long;

int ____ = std::cin.tie(nullptr)->sync_with_stdio(false);

// END OF HEADER | Author: Roger Young

inline constexpr int has_single_bit(int x) {
	return !(x & (x - 1));
}

inline int bit_ceil(int x) {
	int m = 1;
	while (m < x)
		m <<= 1;
	return m;
}

using i8 = signed char;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;

#define all(x) x.begin(), x.end()

////////////////////////////////

const i32 P = 998244353, N = 1 << 21;

i32 qpow(i32 a, i64 b = P - 2, i32 m = P) {
	i32 ret = 1 % m;
	for (; b > 0; b /= 2) {
		if (b % 2 == 1)
			ret = 1ll * ret * a % m;
		a = 1ll * a * a % m;
	}
	return ret;
}

inline i32 mo(i32 x) {
	return x >= P ? x - P : x;
}

std::vector<i32> w{1}; // revw!!!

void pre_w(i32 n) {
	i32 l = w.size(), l2 = l * 2;
	if (n <= l)
		return;
	w.resize(l2);
	i32 p = qpow(3, (P - 1) / l2 / 2);
	for (i32 i = l; i < l2; i++) {
		w[i] = 1ll * w[i - l] * p % P;
	}
	pre_w(n);
}

static i32 ntt_size = 0;

void ntt(i32 *f, i32 n) { // dit
	assert(has_single_bit(n));
	pre_w(n), ntt_size += n;
	static std::array<u64, N> e;
	std::copy_n(f, n, e.data());
	for (i32 l = n / 2; l; l /= 2)
		for (i32 i = 0, *pw = &w[i]; i != n; i += l * 2, pw++)
			for (i32 j = 0; j != l; j++) {
				u64 x = e[i + j];
				i32 y = 1ll * *pw * e[i + j + l] % P;
				e[i + j] = x + y, e[i + j + l] = x - y + P;
			}
	for (i32 i = 0; i < n; i++)
		f[i] = e[i] % P;
}

void intt(i32 *f, i32 n) { // dif
	assert(has_single_bit(n));
	pre_w(n), ntt_size += n;
	for (i32 l = 1; l != n; l *= 2)
		for (i32 i = 0, *pw = &w[i]; i != n; i += l * 2, pw++)
			for (i32 j = 0; j != l; j++) {
				u64 x = f[i + j], y = f[i + j + l];
				f[i + j + l] = 1ll * (x - y + P) * *pw % P;
				f[i + j] = mo(x + y);
			}
	const i32 ivn = P - (P - 1) / n;
	for (i32 i = 0; i < n; i++)
		f[i] = 1ll * f[i] * ivn % P;
	std::reverse(f + 1, f + n);
}

void poly_multiply(u32 *a, i32 n, u32 *b, i32 m, u32 *c) {
	static i32 f[N], g[N];
	n++, m++;
	std::memset(f, 0, sizeof(f));
	std::memset(g, 0, sizeof(f));
	std::copy_n(a, n, f);
	std::copy_n(b, m, g);
	i32 u = bit_ceil(n + m - 1);
	ntt(f, u), ntt(g, u);
	for (i32 i = 0; i < u; i++)
		f[i] = 1ll * f[i] * g[i] % P;
	intt(f, u);
	std::copy_n(f, n + m, c);
}

// int main() {
// 	int n, m;
// 	std::cin >> n >> m;
// 	std::vector<u32> f(n), g(m), h(n + m - 1);
// 	for (auto &i : f)
// 		std::cin >> i;
// 	for (auto &i : g)
// 		std::cin >> i;
// 	poly_multiply(f.data(), n - 1, g.data(), m - 1, h.data());
// 	for (auto i : h) {
// 		std::cout << i << ' ';
// 	}
// 	return 0;
// }

评测结果