Submission #70987605

---

Source Code Expand

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

namespace IO {
	template<typename T> inline void read(T &x) {
		bool f = 1;
		x = 0;
		char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = 0;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
		x = f ? x : -x;
	}
	template<typename T> inline void write(T x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(('0' + x % 10));
	}
	template <typename T, typename ...Args> inline
	void read(T &x, Args &...args) {
		read(x);
		read(args...);
	}
	template<typename T> inline void write(T x, char c) {
		write(x);
		putchar(c);
	}
}
using namespace IO;
using ll = long long;
const ll INF = 1e18;
const int MOD = 998244353;
const ll G = 3;

ll modpow(ll a, ll e) {
	ll r = 1;
	while (e) {
		if (e & 1) r = r * a % MOD;
		a = a * a % MOD;
		e >>= 1;
	}
	return r;
}

void ntt(vector<ll> & a, bool invert) {
	int n = a.size();
	static vector<int> rev;
	static vector<ll> roots{0, 1};
	if ((int)rev.size() != n) {
		int k = __builtin_ctz(n);
		rev.assign(n, 0);
		for (int i = 0; i < n; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
	}
	for (int i = 0; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
	if ((int)roots.size() < n) {
		int k = __builtin_ctz(roots.size());
		roots.resize(n);
		while ((1 << k) < n) {
			ll z = modpow(G, (MOD - 1) >> (k + 1));
			for (int i = 1 << (k - 1); i < (1 << k); ++i) {
				roots[2 * i] = roots[i];
				roots[2 * i + 1] = roots[i] * z % MOD;
			}
			++k;
		}
	}
	for (int len = 1; len < n; len <<= 1) {
		for (int i = 0; i < n; i += 2 * len) {
			for (int j = 0; j < len; ++j) {
				ll u = a[i + j];
				ll v = a[i + j + len] * roots[len + j] % MOD;
				a[i + j] = u + v < MOD ? u + v : u + v - MOD;
				a[i + j + len] = u - v >= 0 ? u - v : u - v + MOD;
			}
		}
	}
	if (invert) {
		reverse(a.begin() + 1, a.end());
		ll inv_n = modpow(n, MOD - 2);
		for (int i = 0; i < n; i++) a[i] = a[i] * inv_n % MOD;
	}
}

vector<ll> multiply_ntt(const vector<ll>& a, const vector<ll>& b) {
	int n = a.size(), m = b.size();
	if (!n || !m) return {};
	int need = n + m - 1;
	int sz = 1;
	while (sz < need) sz <<= 1;
	vector<ll> fa(sz), fb(sz);
	for (int i = 0; i < n; i++) fa[i] = a[i] % MOD;
	for (int i = 0; i < m; i++) fb[i] = b[i] % MOD;
	ntt(fa, false);
	ntt(fb, false);
	for (int i = 0; i < sz; i++) fa[i] = fa[i] * fb[i] % MOD;
	ntt(fa, true);
	fa.resize(need);
	return fa;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, M;
	cin >> N >> M;
	vector<int> A(N), B(M);
	int maxA = 0, maxB = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		maxA = max(maxA, A[i]);
	}
	for (int j = 0; j < M; j++) {
		cin >> B[j];
		maxB = max(maxB, B[j]);
	}

	int LIM = maxA + maxB + 5;
	vector<ll> fact(LIM), invfact(LIM);
	fact[0] = 1;
	for (int i = 1; i < LIM; i++) fact[i] = fact[i - 1] * i % MOD;
	invfact[LIM - 1] = modpow(fact[LIM - 1], MOD - 2);
	for (int i = LIM - 2; i >= 0; i--) invfact[i] = invfact[i + 1] * (i + 1) % MOD;

	vector<ll> cntA(maxA + 1), cntB(maxB + 1);
	for (int x : A) cntA[x]++;
	for (int b : B) cntB[b]++;

	vector<ll> g(maxB + 1), h(maxA + 1);
	for (int b = 0; b <= maxB; b++) {
		if (cntB[b] == 0) g[b] = 0;
		else g[b] = cntB[b] % MOD * invfact[b] % MOD;
	}
	for (int k = 0; k <= maxA; k++) h[k] = invfact[k];

	vector<ll> conv = multiply_ntt(g, h);

	ll ans = 0;
	for (int x = 0; x <= maxA; x++) {
		ll convx = 0;
		if (x < (int)conv.size()) convx = conv[x];
		ll Sx = fact[x] * convx % MOD;
		if (cntA[x]) {
			ans = (ans + Sx * (cntA[x] % MOD)) % MOD;
		}
	}
	cout << ans % MOD << "\n";
	return 0;
}

Submission Info

Judge Result