代码

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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vint;
typedef vector<vint> vvint;

int read() {
	int a = 0, b = 0; char c = getchar();
	while (c < '0' || c > '9') b ^= (c == '-'), c = getchar();
	while (c >= '0' && c <= '9') a = a * 10 - 48 + c, c = getchar();
	return b ? -a : a;
}

const int mod = 998244353, G = 3, N = 2000005;
void Aem(int &a, int b, int c) { a = (a + b * (ll)c) % mod; }
void Add(int &a, int b) { if ((a += b) >= mod) a -= mod; }
int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
ll pw(ll a, ll k = mod - 2) { ll s = 1; while (k) { if (k & 1) s = s * a % mod; a = a * a % mod; k >>= 1; } return s; }

vint rev[23];
vll w[23];
void init() {
	for (int i = 0; (1 << i) < N * 2; ++i) {
		auto &f = rev[i]; f.resize(1 << i);
		for (int j = 1; j < (1 << i); ++j) f[j] = (f[j >> 1] >> 1) | ((j & 1) << i - 1);
		auto &g = w[i]; g.resize(1 << i); g[0] = 1;
		ll wn = pw(G, (mod - 1) >> i);
		for (int j = 1; j < (1 << i); ++j) g[j] = g[j - 1] * wn % mod;
	} 
}

void dft(vint &a, int flg) {
	int n = a.size(), k = __lg(n);
	for (int i = 0; i < n; ++i) if (rev[k][i] < i) swap(a[i], a[rev[k][i]]);
	for (int l = 2, gl = 1; l <= n; ++gl, l <<= 1) {
		for (int i = 0, kl = (l >> 1); i < n; i += l) {
			for (int j = 0; j < kl; ++j) {
				int v = w[gl][j] * a[i + j + kl] % mod;
				a[i + j + kl] = sub(a[i + j], v);
				Add(a[i + j], v); 
			}
		}
	}
	if (flg == -1) {
		reverse(a.begin() + 1, a.end()); ll in = pw(n);
		for (int &i : a) i = i * in % mod;
	}
}


vint mult(vint a, vint b) {
	if (!a.size() || !b.size()) return vint();
	int m = a.size() + b.size() - 1, n = 1;
	while (n < m) n <<= 1;
	const ll E = 0;
	if (a.size() * (ll)b.size() <= E * n * __lg(n)) {
		vint c(m);
		for (int i = 0; i < a.size(); ++i) for (int j = 0; j < b.size(); ++j) Aem(c[i + j], a[i], b[j]);
		return c;
	}
	a.resize(n), b.resize(n);
	dft(a, 1), dft(b, 1);
	for (int i = 0; i < n; ++i) a[i] = a[i] * (ll)b[i] % mod;
	dft(a, -1); a.resize(m);
	return a;
}

void poly_multiply(unsigned *aa, int n, unsigned *bb, int m, unsigned *cc) {
init();
	++n, ++m;
	vint a(n), b(m);
	for (int i = 0; i < n; ++i) a[i] = aa[i];
	for (int i = 0; i < m; ++i) b[i] = bb[i];
	vint c = mult(a, b);
	for (int i = 0; i < n + m - 1; ++i) cc[i] = c[i];
}

评测结果