[LOJ#3119][CTS2019]随機立方體（容斥）

Address

• 洛谷 P5400
• LOJ #3119

Solution

• 考慮容斥
• 具體地，用「選出 k k k 個格子，這 k k k 個格子極大的機率之和」 × C k k \times C_k^k ×Ckk​
• 減去「選出 k + 1 k+1 k+1 個格子，這 k + 1 k+1 k+1 個格子極大的機率之和」 × C k + 1 k \times C_{k+1}^k ×Ck+1k​
• 再加上「選出 k + 2 k+2 k+2 個格子，這 k + 2 k+2 k+2 個格子極大的機率之和」 × C k + 2 k \times C_{k+2}^k ×Ck+2k​
• 以此類推直到 min ⁡ ( n , m , l ) \min(n,m,l) min(n,m,l)
• 問題轉化為對于所有的 i ∈ [ k , min ⁡ ( n , m , l ) ] i\in[k,\min(n,m,l)] i∈[k,min(n,m,l)] ，求選出 i i i 個格子，使得這 i i i 個格子極大的機率之和（換句話說，就是對于所有選出 i i i 個格子的方案，已經選出的 i i i 個格子為極大的機率之和）
• 顯然地，所有極大的格子都滿足 x x x 互不相同， y y y 互不相同， z z z 互不相同
• 同時，我們容易得到，這 i i i 個格子具體取在哪些位置，與這 i i i 個格子為極大的機率無關
• 于是假設我們确定了這 i i i 個格子的位置以及大小順序，定義第 1 1 1 ， 2 2 2 ， 3 3 3 …個格子為上面填的數第 1 1 1 ， 2 2 2 ， 3 3 3 …大的格子
• 這樣對于每個 x y z xyz xyz 坐标之一與這 i i i 個格子之一相等的格子，都存在一個限制，即這個格子上的數不超過選出的第 t t t 個格子上的數
• 可以計算出，這樣的格子總數為 n m l − ( n − i ) ( m − i ) ( l − i ) nml-(n-i)(m-i)(l-i) nml−(n−i)(m−i)(l−i)
• 由于我們已經确定了這 i i i 個格子的大小順序，是以選出的第 1 1 1 個格子應該是這 n m l − ( n − i ) ( m − i ) ( l − i ) nml-(n-i)(m-i)(l-i) nml−(n−i)(m−i)(l−i) 個中的最大者
• 易得第 1 1 1 個格子為最大值的機率為
• 1 n m l − ( n − i ) ( m − i ) ( l − i ) \frac1{nml-(n-i)(m-i)(l-i)} nml−(n−i)(m−i)(l−i)1​
• 而如果這樣，那麼對于一個格子（不為第 1 1 1 個格子），如果它與第 1 1 1 個格子存在至少一個坐标相等，而與第 2 2 2 到第 i i i 個格子不存在任一坐标相等，則這個格子可以在之前的條件下任意取
• 這樣還剩下 n m l − ( n − ( i − 1 ) ) ( m − ( i − 1 ) ) ( l − ( i − 1 ) ) nml-(n-(i-1))(m-(i-1))(l-(i-1)) nml−(n−(i−1))(m−(i−1))(l−(i−1)) 個格子需要處理
• 顯然，這時候第 2 2 2 個格子需要成為這些格子中填數最大的格子
• 機率為
• 1 n m l − ( n − ( i − 1 ) ) ( m − ( i − 1 ) ) ( l − ( i − 1 ) ) \frac1{nml-(n-(i-1))(m-(i-1))(l-(i-1))} nml−(n−(i−1))(m−(i−1))(l−(i−1))1​
• 以此類推。這樣我們得出了：在 i i i 個格子的相對大小及位置确定的情況下，這 i i i 個格子都為極大的機率為
• ∏ j = 1 i 1 n m l − ( n − j ) ( m − j ) ( l − j ) \prod_{j=1}^i\frac1{nml-(n-j)(m-j)(l-j)} j=1∏i​nml−(n−j)(m−j)(l−j)1​
• 回到前面，由于我們需要确定這 i i i 個格子的相對大小及位置，故「選出 i i i 個格子，這 i i i 個格子極大的機率之和」等于
• A n i A m i A l i ∏ j = 1 i 1 n m l − ( n − j ) ( m − j ) ( l − j ) A_n^i A_m^iA_l^i\prod_{j=1}^i\frac1{nml-(n-j)(m-j)(l-j)} Ani​Ami​Ali​j=1∏i​nml−(n−j)(m−j)(l−j)1​
• 是以最終答案
• ∑ i = k min ⁡ ( n , m , k ) ( − 1 ) i − k C i k A n i A m i A l i ∏ j = 1 i 1 n m l − ( n − j ) ( m − j ) ( l − j ) \sum_{i=k}^{\min(n,m,k)}(-1)^{i-k}C_i^kA_n^iA_m^iA_l^i\prod_{j=1}^i\frac1{nml-(n-j)(m-j)(l-j)} i=k∑min(n,m,k)​(−1)i−kCik​Ani​Ami​Ali​j=1∏i​nml−(n−j)(m−j)(l−j)1​
• 注意到如果逐個預處理 n m l − ( n − i ) ( m − i ) ( l − i ) nml-(n-i)(m-i)(l-i) nml−(n−i)(m−i)(l−i) 的字首積的逆元，那麼你會得到 80 80 80 分的高分
• 需要一個小 trick ：我們預處理 n n n 個數的字首積的逆元時，可以先求出所有 n n n 個數的積的逆元，那麼可以得到
• f ( i ) = f ( i + 1 ) a i + 1 f(i)=f(i+1)a_{i+1} f(i)=f(i+1)ai+1​
• f ( i ) f(i) f(i) 為前 i i i 個數積的逆元， a i a_i ai​ 為第 i i i 個數
• 實作 O ( n ) O(n) O(n) 預處理逆元
• 複雜度 O ( T min ⁡ ( n , m , l ) ) O(T\min(n,m,l)) O(Tmin(n,m,l))

Code

#include <bits/stdc++.h>

inline int read()
{
	int res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	return bo ? ~res + 1 : res;
}

template <class T>
inline T Min(const T &a, const T &b, const T &c)
{
	T x = a;
	if (b < x) x = b;
	if (c < x) x = c;
	return x;
}

const int N = 5e6 + 5, ZZQ = 998244353;

int n, m, l, k, a[N], fac[N], inv[N], inva[N];

int qpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = 1ll * res * a % ZZQ;
		a = 1ll * a * a % ZZQ;
		b >>= 1;
	}
	return res;
}

int A(int n, int m)
{
	return 1ll * fac[n] * inv[n - m] % ZZQ;
}

int C(int n, int m)
{
	return 1ll * fac[n] * inv[m] % ZZQ * inv[n - m] % ZZQ;
}

void work()
{
	int ans = 0, qr = 1;
	n = read(); m = read(); l = read(); k = read();
	for (int i = 1; i <= Min(n, m, l); i++)
		a[i] = (1ll * n * m % ZZQ * l % ZZQ - 1ll * (n - i) * (m - i)
			% ZZQ * (l - i) % ZZQ + ZZQ) % ZZQ,
				qr = 1ll * qr * a[i] % ZZQ;
	inva[Min(n, m, l)] = qpow(qr, ZZQ - 2);
	for (int i = Min(n, m, l) - 1; i >= 0; i--)
		inva[i] = 1ll * inva[i + 1] * a[i + 1] % ZZQ;
	for (int i = k; i <= Min(n, m, l); i++)
	{
		int delta = 1ll * A(n, i) * A(m, i) % ZZQ * A(l, i)
			% ZZQ * inva[i] % ZZQ * C(i, k) % ZZQ;
		if (i - k & 1) ans = (ans - delta + ZZQ) % ZZQ;
		else ans = (ans + delta) % ZZQ;
	}
	printf("%d\n", ans);
}

int main()
{
	fac[0] = inv[0] = inv[1] = 1;
	for (int i = 1; i <= 5000000; i++)
		fac[i] = 1ll * fac[i - 1] * i % ZZQ;
	for (int i = 2; i <= 5000000; i++)
		inv[i] = 1ll * (ZZQ - ZZQ / i) * inv[ZZQ % i] % ZZQ;
	for (int i = 2; i <= 5000000; i++)
		inv[i] = 1ll * inv[i] * inv[i - 1] % ZZQ;
	int T = read();
	while (T--) work();
	return 0;
}