组合数学 (Combinatorics)¶

在算法竞赛中，组合计数问题极为频繁。通常需要在给定素数模数 \(p\)（如 \(10^9+7\) 或 \(998244353\)）下快速计算组合数 \(\binom{n}{k} = C_n^k\)。

阶乘与逆元预处理 (O(n) 预处理，O(1) 查询)¶

当 \(n \le 10^6\) 且模数 \(MOD\) 为质数时，预处理阶乘及其逆元是计算组合数的最优方式。

#include <vector>

struct Combinatorics {
    int n;
    long long mod;
    std::vector<long long> fact;
    std::vector<long long> inv_fact;

    long long power(long long a, long long b) const {
        long long res = 1;
        a %= mod;
        while (b > 0) {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    Combinatorics(int n, long long mod = 1e9 + 7) : n(n), mod(mod), fact(n + 1), inv_fact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) {
            fact[i] = fact[i - 1] * i % mod;
        }
        // 预处理末尾逆元
        inv_fact[n] = power(fact[n], mod - 2);
        for (int i = n - 1; i >= 0; --i) {
            inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod;
        }
    }

    // 计算 C(n, k)
    long long C(int n, int k) const {
        if (k < 0 || k > n) return 0;
        return fact[n] * inv_fact[k] % mod * inv_fact[n - k] % mod;
    }

    // 计算排列数 P(n, k)
    long long P(int n, int k) const {
        if (k < 0 || k > n) return 0;
        return fact[n] * inv_fact[n - k] % mod;
    }
};

卢卡斯定理 (Lucas' Theorem)¶

当 \(n, k\) 极大（例如 \(10^{18}\)），而模数 \(p\) 是较小质数（例如 \(p \le 10^5\)）时，适用卢卡斯定理：

\[ \binom{n}{k} \equiv \binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor} \binom{n \bmod p}{k \bmod p} \pmod p \]

时间复杂度为 \(\mathcal{O}(p + \log_p n)\)。

long long C_small(long long n, long long k, long long p) {
    if (k < 0 || k > n) return 0;
    long long num = 1, den = 1;
    for (int i = 0; i < k; ++i) {
        num = num * (n - i) % p;
        den = den * (i + 1) % p;
    }
    // 求 den 的逆元
    auto power = [](long long a, long long b, long long mod) {
        long long res = 1;
        while (b > 0) {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    };
    return num * power(den, p - 2, p) % p;
}

long long lucas(long long n, long long k, long long p) {
    if (k == 0) return 1;
    return lucas(n / p, k / p, p) * C_small(n % p, k % p, p) % p;
}

LeetCode 经典真题精选与题解提示¶

LeetCode 62 - 不同路径 (Unique Paths) 中等
提示

网格移动与基础组合数。
- 从 \(m \times n\) 网格左上角到达右下角，总共必须向右移动 \(n - 1\) 步、向下移动 \(m - 1\) 步，总步数为 \(m + n - 2\)。
- 答案即为在总步数中选取向下步数的组合数 \(\binom{m + n - 2}{m - 1}\)，利用组合数乘除公式单次 \(\mathcal{O}(\min(m, n))\) 计算即可。
LeetCode 1359 - 有效的快递序列数目 (Count All Valid Pickup and Delivery Options) 困难
提示

空隙插入法与阶乘组合。
- 考虑逐步加入每个订单对 \((P_i, D_i)\)：前 \(i - 1\) 份订单已排布为 \(2(i - 1)\) 个位置，在其中插入 \(P_i\) 和 \(D_i\)（且 \(P_i\) 必须在 \(D_i\) 前面）。
- 在 \(2i - 1\) 个空隙中，若 \(P_i, D_i\) 放在不同空隙有 \(\binom{2i - 1}{2}\) 种选法；若放在同一空隙有 \(2i - 1\) 种选法。两者之和为 \(\frac{(2i - 1)(2i)}{2} = i(2i - 1)\)。
- 最终总序列数为 \(\prod_{i=1}^{n} i(2i - 1) \pmod{10^9 + 7}\)。
LeetCode 920 - 音乐播放列表 (Number of Music Playlists) 困难
提示

带冷却限制的组合 DP / 斯特林数推广。
- 设 \(dp[i][j]\) 表示当前已播放 \(i\) 首歌，且恰好包含 \(j\) 首不同的曲目。
- 状态转移分为两类：
  1. 当前播放了一首从未听过的新歌：从剩余的 \(n - (j - 1)\) 首中挑选，\(dp[i][j] += dp[i - 1][j - 1] \times (n - j + 1)\)；
  2. 当前播放了一首之前听过的老歌：为满足冷却限制 \(k\)，最近播放的 \(k\) 首不可选，故可选的老歌数量为 \(\max(0, j - k)\)，转移为 \(dp[i][j] += dp[i - 1][j] \times \max(0, j - k)\)。
LeetCode 1866 - 恰有 K 根木棍可以看到的排列数 (Number of Ways to Rearrange Sticks With K Sticks Visible) 困难
提示

第一类斯特林数 (Stirling Numbers of the First Kind)。
- 考虑长度最短的木棍（长度 1）：
  - 若将其放在最左侧，则该木棍必定可见，剩余 \(n - 1\) 根木棍需贡献 \(k - 1\) 根可见，方案数为 \(dp[n - 1][k - 1]\)；
  - 若将其放在其余 \(n - 1\) 个位置中的任意一个，它必定被左侧更长的木棍遮挡而不可见，剩余木棍仍需贡献 \(k\) 根可见，方案数为 \((n - 1) \times dp[n - 1][k]\)。
- 转移方程 \(dp[n][k] = dp[n - 1][k - 1] + (n - 1) \cdot dp[n - 1][k]\)，即为第一类无符号斯特林数 \(\begin{bmatrix} n \\ k \end{bmatrix}\)。
LeetCode 1643 - 第 K 条最小指令 (Kth Smallest Instructions) 困难
提示

字典序贪心逐位确定 + 组合数分支判断。
- 需要走 \(h\) 步 'H' 和 \(v\) 步 'V'，字典序中 'H' < 'V'；
- 当前位尝试填 'H'：若后续剩余步数的组合数 \(\binom{h - 1 + v}{h - 1} \ge k\)，说明第 \(k\) 小路径落在 'H' 分支内，当前位必填 'H'，令 \(h -= 1\)；
- 否则必填 'V'，令 \(k -= \binom{h - 1 + v}{h - 1}\) 且 \(v -= 1\)。
LeetCode 2514 - 统计同位异构字符串数目 (Count Anagrams) 困难
提示

多重集合排列数公式与逆元乘法。
- 句子中每个单词相互独立，总方案数为各单词重排数的乘积；
- 对于长度为 \(L\)、各字符出现频次为 \(c_1, c_2, \dots, c_m\) 的单词，由多重集合排列数公式其同位异构数为：\(\frac{L!}{c_1! \cdot c_2! \cdots c_m!} \pmod{10^9 + 7}\)；
- 预处理阶乘及阶乘逆元，单次单词计算 \(\mathcal{O}(L)\)。