题目大意

给定 $n \times m \times l$ 的立方体，将 $1 \sim nml$ 随机填入每个格子。定义极大值为比它所在行、所在列、所在高的所有其他数都大的数。求恰好有 $k$ 个极大值的概率，对 $998244353$ 取模。

数据范围：$n, m, l \leq 5 \times 10^6$，$k \leq 100$，$T \leq 10$。

---

问题分析

极大值的性质

• 一个格子 $(x, y, z)$ 是极大值，当且仅当它的数值大于：
  • 所有 $(x, y', z')$ 其中 $y' \neq y$ 或 $z' \neq z$
  • 所有 $(x', y, z')$ 其中 $x' \neq x$ 或 $z' \neq z$
  • 所有 $(x', y', z)$ 其中 $x' \neq x$ 或 $y' \neq y$
• 即比所有与它至少共享一维坐标的格子数值都大

极大值之间的关系

• 两个极大值不能在同一行、同一列或同一高
• 因此最多有 $\min(n, m, l)$ 个极大值

---

核心思路：容斥原理

设 $F(i)$ 表示至少 $i$ 个位置是极大值的概率。

根据容斥原理，恰好 $k$ 个极大值的概率为：

$$P(\text{exactly } k) = \sum_{i=k}^{N} (-1)^{i-k} \binom{i}{k} F(i) $$

其中 $N = \min(n, m, l)$。

---

计算 $F(i)$

关键观察

考虑按数值从大到小依次确定极大值的位置。

设已经确定了 $j-1$ 个极大值，现在要确定第 $j$ 个极大值：

• 可选的极大值位置数：$(n-j+1)(m-j+1)(l-j+1)$

  • 因为不能与已有的 $j-1$ 个极大值同行、同列、同高

• 可用的数值范围：$nml - (n-j)(m-j)(l-j) - (j-1)$

  • 总格子数 $nml$
  • 减去不受影响的格子数 $(n-j)(m-j)(l-j)$
  • 再减去已使用的 $j-1$ 个极大值

概率递推

因此第 $j$ 步成功的概率为：

$$\frac{(n-j+1)(m-j+1)(l-j+1)}{nml - (n-j)(m-j)(l-j) - (j-1)} $$

于是：

$$F(i) = \prod_{j=1}^{i} \frac{(n-j+1)(m-j+1)(l-j+1)}{nml - (n-j)(m-j)(l-j) - (j-1)} $$

---

算法实现

预处理

const int MOD = 998244353;
const int MAXK = 105;

int fac[MAXK], invfac[MAXK];

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

void init() {
    fac[0] = 1;
    for (int i = 1; i < MAXK; i++) 
        fac[i] = 1LL * fac[i-1] * i % MOD;
    invfac[MAXK-1] = qpow(fac[MAXK-1], MOD-2);
    for (int i = MAXK-2; i >= 0; i--)
        invfac[i] = 1LL * invfac[i+1] * (i+1) % MOD;
}

int C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return 1LL * fac[n] * invfac[k] % MOD * invfac[n-k] % MOD;
}

主求解函数

int solve(int n, int m, int l, int k) {
    int N = min({n, m, l});
    if (k > N) return 0;
    
    vector<int> F(N + 1);
    F[0] = 1;
    
    // 计算 F(i) = ∏ A_j / B_j
    for (int i = 1; i <= N; i++) {
        long long A = 1LL * (n - i + 1) * (m - i + 1) % MOD;
        A = A * (l - i + 1) % MOD;
        
        long long B = (1LL * n * m % MOD * l) % MOD;
        B = (B - 1LL * (n - i) * (m - i) % MOD * (l - i) % MOD + MOD) % MOD;
        B = (B - (i - 1) + MOD) % MOD;
        
        F[i] = 1LL * F[i-1] * A % MOD * qpow(B, MOD-2) % MOD;
    }
    
    // 容斥计算答案
    int ans = 0;
    for (int i = k; i <= N; i++) {
        int sign = (i - k) % 2 ? MOD - 1 : 1;
        int term = 1LL * C(i, k) * sign % MOD;
        ans = (ans + 1LL * term * F[i]) % MOD;
    }
    
    return ans;
}

---

复杂度分析

• 预处理：$O(k)$ 计算阶乘和逆元
• 每次查询：$O(k)$ 计算 $F(i)$ 和容斥
• 总复杂度：$O(T \cdot k)$，可以高效处理 $n, m, l$ 高达 $5\times 10^6$ 的情况

---

关键点与技巧

1. 容斥原理：将"恰好 $k$ 个"转化为"至少 $i$ 个"的线性组合
2. 逐步构造：按数值从大到小确定极大值，分析每一步的可行选择
3. 独立概率乘积：利用条件独立性将联合概率分解为条件概率的乘积
4. 模运算优化：预处理逆元，使用快速幂计算乘法逆元
5. 利用 $k$ 小的特点：将复杂度从 $O(n)$ 降为 $O(k)$

---

总结

本题通过巧妙的概率分析和容斥原理，将复杂的三维极大值计数问题转化为简单的乘积形式。核心在于发现极大值之间的制约关系，以及按数值顺序构造的递推方法。最终算法在时间和空间上都达到了最优复杂度，能够处理极限数据范围。