组合数学 (Combinatorics)¶
在算法竞赛中，组合计数问题极为频繁。通常需要在给定素数模数 \(p\)（如 \(10^9+7\) 或 \(998244353\)）下快速计算组合数 \(\binom{n}{k} = C_n^k\)。
阶乘与逆元预处理 (\(\mathcal{O}(n)\) 预处理，\(\mathcal{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\) 首不同的曲目。
- 状态转移分为两类：
- 当前播放了一首从未听过的新歌：从剩余的 \(n - (j - 1)\) 首中挑选，\(dp[i][j] += dp[i - 1][j - 1] \times (n - j + 1)\)；
- 当前播放了一首之前听过的老歌：为满足冷却限制 \(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}\)。
- 考虑长度最短的木棍（长度 1）：