Submission #70982916

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e5 + 10, P = 998244353;
const int g = 3;
const int inv_g = 332748118;

int n, m, a[N], b[N];

int fpm(int a, int b = P - 2, int p = P) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % p;
		b >>= 1, a = 1ll * a * a % p;
	}
	return res;
}

int fac[N], inv[N];

void init(int n = N - 1) {
	fac[0] = 1;
	for (int i = 1; i <= n; ++ i ) fac[i] = 1ll * fac[i - 1] * i % P;
	inv[n] = fpm(fac[n]);
	for (int i = n - 1; ~i; -- i ) inv[i] = 1ll * inv[i + 1] * (i + 1) % P;
}

void ntt(vector<int>& a, int type) {
	int n = a.size();
	vector<int> rev(n);
	
	for (int i = 0; i < n; ++ i ) {
	  rev[i] = rev[i >> 1] >> 1;
	  if (i & 1) rev[i] |= n >> 1;
	}
	
	for (int i = 0; i < n; ++ i ) {
	  if (i < rev[i]) swap(a[i], a[rev[i]]);
	}
	
	for (int mid = 1; mid < n; mid <<= 1) {
	  long long w_m = fpm(type == 1 ? g : inv_g, (P - 1) / (mid * 2)); // 单位根
	  for (int j = 0; j < n; j += mid * 2) {
	    long long w = 1;
	    for (int k = 0; k < mid; ++k) {
	      long long u = a[j + k];
	      long long v = w * a[j + k + mid] % P;
	      a[j + k] = (u + v) % P;
	      a[j + k + mid] = (u - v + P) % P;
	      w = w * w_m % P;
	    }
	  }
	}
	
	// 逆变换需乘以n的逆元（模P）
	if (type == -1) {
	  long long inv_n = fpm(n, P - 2);
	  for (int i = 0; i < n; ++ i ) {
	    a[i] = a[i] * inv_n % P;
	  }
	}
}

vector<int> multi(vector<int> A, vector<int> B) {
	int n = A.size(), m = B.size();
	if (n == 0 || m == 0) return {};
	
	int res_len = n + m - 1;
	int lim = 1;
	while (lim < res_len) lim <<= 1;
	
	A.resize(lim, 0);
	B.resize(lim, 0);
	for (int& x : A) x = (x % P + P) % P;
	for (int& x : B) x = (x % P + P) % P;
	
	ntt(A, 1);
	ntt(B, 1);
	
	vector<int> C(lim);
	for (int i = 0; i < lim; ++ i ) {
		C[i] = 1LL * A[i] * B[i] % P;
	}
	
	ntt(C, -1);
	
	C.resize(res_len);
	return C;
}
signed main() {
	init();
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i ) cin >> a[i];
	for (int i = 1; i <= m; ++ i ) cin >> b[i];
	
	vector<int> A(N), B(N);
	for (int i = 1; i <= n; ++ i ) (A[a[i]] += fac[a[i]]) %= P;
	for (int i = 1; i <= m; ++ i ) (B[N - 1 - b[i]] += inv[b[i]]) %= P;
	vector<int> C = multi(A, B);
	
	int res = 0;
	for (int i = 0; i <= 5e5; ++ i ) {
		res += 1ll * inv[i] * C[i + N - 1] % P;
		res %= P;
		// if (C[i + N - 1]) {
		//   cout << 
		// }
	}
	cout << res;
	
	return 0;
}

Submission Info

Judge Result