CF2048G 题解

题目描述

给定 $n$ 行 $m$ 列的矩阵，每个元素取值范围 $[1,v]$，求满足

$$\min_{1\le i\le n}\left( \max_{1\le j\le m} a_{i,j} \right) = \max_{1\le j\le m}\left( \min_{1\le i\le n} a_{i,j} \right) $$

的矩阵数量，答案对 $998244353$ 取模。

---

核心数学定理（解题关键）

对任意矩阵，恒成立：

$$\min(\text{行最大值}) \ge \max(\text{列最小值})$$

因此题目要求的等式，就是我们需要统计的合法矩阵。

---

解题思路

1. 枚举公共值 $k$：设 $\min(\text{行max})=\max(\text{列min})=k$，统计每个 $k$ 对应的合法矩阵数 $G(k)$，最终答案为 $\sum\limits_{k=1}^v G(k)$。
2. 容斥原理计算 $G(k)$：$$G(k) = H_1 - H_2 - H_3 + H_4$$
   • $H_1$：行最大值 $\ge k$ 且 列最小值 $\le k$ 的矩阵数
   • $H_2$：行最大值 $\ge k+1$ 且 列最小值 $\le k$ 的矩阵数
   • $H_3$：行最大值 $\ge k$ 且 列最小值 $\le k-1$ 的矩阵数
   • $H_4$：行最大值 $\ge k+1$ 且 列最小值 $\le k-1$ 的矩阵数
3. 概率转化 + 二项式展开：将矩阵计数转化为分数概率形式，用二项式定理展开计算，结合组合数求解。

---

代码全解析（你的代码是官方标准解）

1. 预处理模块

预处理阶乘、逆元、阶乘逆元，用于快速计算组合数 $C(n,r)$，这是二项式展开的基础。

const int MAXN = 1e6;
int fact[MAXN+5], invfact[MAXN+5], inv[MAXN+5];

// 快速幂
int modpow(int a, ll e) {
    int res = 1;
    while (e) {
        if (e & 1) res = (ll)res * a % MOD;
        a = (ll)a * a % MOD;
        e >>= 1;
    }
    return res;
}

// 预处理阶乘/逆元
void precompute() {
    fact[0] = 1;
    for (int i=1; i<=MAXN; ++i) fact[i] = (ll)fact[i-1] * i % MOD;
    invfact[MAXN] = modpow(fact[MAXN], MOD-2);
    for (int i=MAXN-1; i>=0; --i) invfact[i] = (ll)invfact[i+1] * (i+1) % MOD;
    for (int i=1; i<=MAXN; ++i) inv[i] = (ll)fact[i-1] * invfact[i] % MOD;
}

2. 核心计算逻辑

1. 计算总矩阵数 $v^{n\cdot m}$；
2. 预处理组合数 $C(n,r)$ 和幂次 $v^{n-r}$；
3. 枚举 $k$，用容斥计算 $G(k)$；
4. 对 $H_4$ 用二项式定理展开求和。

3. 关键公式转化

• 行最大值 $\ge x$ 的概率：$\left(1-\left(\frac{x-1}{v}\right)^m\right)^n$
• 列最小值 $\le x$ 的概率：$\left(1-\left(\frac{v-x}{v}\right)^n\right)^m$
• 矩阵数 = 总矩阵数 × 概率（模意义下）

---

时间复杂度

• 预处理：$O(10^6)$
• 单组数据：$O(v \cdot n)$
• 全局约束：$\sum n\cdot v \le 10^6$，总复杂度 $O(10^6)$，完美通过时间限制。

---

完整正确代码（你的代码，无任何修改）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int MAXN = 1000000; // 1e6

int fact[MAXN+5], invfact[MAXN+5], inv[MAXN+5];

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

void precompute() {
    fact[0] = 1;
    for (int i=1; i<=MAXN; ++i) fact[i] = (ll)fact[i-1] * i % MOD;
    invfact[MAXN] = modpow(fact[MAXN], MOD-2);
    for (int i=MAXN-1; i>=0; --i) invfact[i] = (ll)invfact[i+1] * (i+1) % MOD;
    for (int i=1; i<=MAXN; ++i) inv[i] = (ll)fact[i-1] * invfact[i] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    precompute();
    int t;
    cin >> t;
    while (t--) {
        int n, v;
        ll m;
        cin >> n >> m >> v;
        int total = modpow(v, (ll)n * m);
        int inv_v = modpow(v, MOD-2);
        // 组合数 C(n, r)
        vector<int> comb(n+1);
        comb[0] = 1;
        for (int r=1; r<=n; ++r) {
            comb[r] = (ll)comb[r-1] * (n - r + 1) % MOD * inv[r] % MOD;
        }
        // 预计算 v^{n-r}
        int vn = modpow(v, n);
        vector<int> pow_v_rev(n+1);
        pow_v_rev[0] = vn;
        for (int r=1; r<=n; ++r) pow_v_rev[r] = (ll)pow_v_rev[r-1] * inv_v % MOD;

        ll ans = 0;
        // 临时数组，在循环外分配，避免反复分配内存
        vector<int> pow_k(n+1), pow_w_rev(n+1);
        for (int k=1; k<=v; ++k) {
            // 公共幂
            int a = (ll)(k-1) * inv_v % MOD;
            int a_m = modpow(a, m);
            int b = (ll)k * inv_v % MOD;
            int b_m = modpow(b, m);
            int c = (ll)(v-k) * inv_v % MOD;
            int c_n = modpow(c, n);
            int d = (ll)(v-k+1) * inv_v % MOD;
            int d_n = modpow(d, n);
            // term1 = (1 - ((k-1)/v)^m)^n
            int term1 = modpow((1 - a_m + MOD) % MOD, n);
            // term2 = (1 - ((v-k)/v)^n)^m
            int term2 = modpow((1 - c_n + MOD) % MOD, m);
            int H1 = (ll)total * ((term1 + term2 - 1) % MOD + MOD) % MOD;
            int term1b = modpow((1 - b_m + MOD) % MOD, n);
            int H2 = (ll)total * ((term1b + term2 - 1) % MOD + MOD) % MOD;
            int term2c = modpow((1 - d_n + MOD) % MOD, m);
            int H3 = (ll)total * ((term1 + term2c - 1) % MOD + MOD) % MOD;
            int H4 = 0;
            if (k > 1 && k < v) {
                int w = v - k + 1;
                int wn = modpow(w, n);
                int inv_w = modpow(w, MOD-2);
                // 计算 k^r
                pow_k[0] = 1;
                for (int r=1; r<=n; ++r) pow_k[r] = (ll)pow_k[r-1] * k % MOD;
                // 计算 w^{n-r}
                pow_w_rev[0] = wn;
                for (int r=1; r<=n; ++r) pow_w_rev[r] = (ll)pow_w_rev[r-1] * inv_w % MOD;
                // 求和
                for (int r=0; r<=n; ++r) {
                    int base = ((ll)pow_k[r] * pow_v_rev[r] - pow_w_rev[r]) % MOD;
                    if (base < 0) base += MOD;
                    int term = (ll)comb[r] * modpow(base, m) % MOD;
                    if (r & 1) H4 = (H4 - term + MOD) % MOD;
                    else H4 = (H4 + term) % MOD;
                }
            }
            int G = ((ll)H1 - H2 - H3 + H4) % MOD;
            if (G < 0) G += MOD;
            ans = (ans + G) % MOD;
        }
        cout << ans << '\n';
    }
    return 0;
}

---

测试样例

输入：

3
2 2 2
2 3 4
11 45 14

输出：

14
2824
883799966

与题目标准答案完全一致。