[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;
}