盛日辉的博客
0%

组合数

发表于 更新于 分类于

在一些计数问题中，有的时候需要预处理组合数。这里有两种方法：

  1. 动态规划（杨辉三角），用于规模较小的情况；
  2. 阶乘 + 逆元，用于规模较大的情况。

动态规划（杨辉三角）

计算 $C(n,k)$ ，从 $n$ 个里面取 $k$ 个，从动态规划的角度来思考可以看成以下两种情况的和：

  1. 第 $n$ 个选，在前 $n-1$ 个里再选 $k-1$ 个；
  2. 第 $n$ 个不选，在前 $n-1$ 个里再选 $k$ 个。

因此，$C(n,k)=C(n-1,k-1) + C(n-1,k)$ ——将杨辉三角“变个形”，可以发现这和杨辉三角的计算规则是一致的。

代码

1
2
3
4
5
6
d = [[0] * (n + 1) for _ in range(n + 1)]
d[0][0] = 1
for i in range(1, n + 1):
    d[i][0] = 1
    for j in range(1, i + 1):
        d[i][j] = (d[i-1][j] + d[i-1][j-1]) % MOD

注意：因为递推式里有 $i-1$ 和 $j -1 $，所以 $i$ 和 $j$ 都是从 $1$ 开始的。也因此，$d[.][0]$ 要另外处理，其值均为 $1$。

阶乘 + 逆元

逆元

「逆元」这东西，我之前学过好几次都学不明白，今天不追究到底跟 ChatGPT 学了之后，算是明白了一些，至少用在算组合数上大概知道怎么回事了。下面根据学习的内容，总结、整理、推导一下。

聊天内容在这里，详细可以回去再看，下面就简单总结性地写。

开始

首先要强调的是，「逆元」是在「模的世界」里才有的东西。之前看其他视频、文章啥的，上来就类比普通数里倒数关系，我觉得是挺不妥、有点摸不着头脑的。有了这个前提之后，我们再来看什么是逆元：

对于一个数 $a$，如果有一个数 $x$，使得 $a \times x \equiv 1 \pmod{MOD}$，就说 $x$ 是 $a$ 的逆元，记作 $inv(a)$。

这定义是我说的，不一定准确，但够用了。

那么逆元有什么用呢？那就是在「模的世界」里代替除法。在「模的世界」中的运算，是没有除法的，而且就算在普通数里，我们也不喜欢除法，尤其是大数的情况下。

举两个例子。

  1. 假设现在 $MOD = 7$ ，我们要计算 $5 \div 3 \equiv \ ? \pmod{7}$。

    1. 第一种思考方式，就是算 $3$ 乘多少模 $7$ 等于 $5$，通过不断试，得到结果是 $4$；
    2. 第二种思考方式就是逆元，因为 $3 \times 5 \equiv 1 \pmod{7}$，所以在模 $7$ 的世界里，$3$ 的逆元是 $5$，那么 $ 5 \div 3 = 5 \times inv(3) = 5 \times 5 \equiv 4 \pmod{7}$，和上一种结果一样。

  2. 假设现在 $MOD = 11$，我们要计算$7 \div 4 \equiv \ ? \pmod{11}$。

    1. 第一种思考方式，就是算 $4$ 乘多少模 $11$ 等于 $7$，通过不断试，得到结果是 $10$；
    2. 第二种思考方式就是逆元，因为 $4 \times 3 \equiv 1 \pmod{11}$，所以在模 $11$ 的世界里，$4$ 的逆元是 $3$，那么 $ 7 \div 4 = 7 \times inv(4) = 7 \times 3 \equiv 10 \pmod{11}$，和上一种结果一样。

用到组合数里

组合数的计算公式：

用 $inv(k!)$ 和 $inv((n-k)!)$ 换掉 $ \div k! $ 和 $(n-k)!$，得到

好啦，这就是后面计算要用到的公式了。

接下来，问题就到了怎么求逆元了。

怎么求

我们要算 $x!$ 的逆元，我们先看这件显然的事情，

瞧啊，这不是除法么，我们在 $MOD$ 的世界里，把它改成逆元的形式，

两边同时再取逆元（这里的运算规则我不会，但 ChatGPT 是这么做的，那我就凭感觉这么做了），

看呐，这不就是个递推式么，那如果我们算出了 $x!$ 的逆元，那不就能一路算出 $(x-1)!, (x-2)!, … 2, 1$ 的逆元了~

那接下来怎么算 $inv(x!)$ 呢？

从 Python3.8 开始，我们可以直接写 $pow(x!, -1, MOD)$，但在 3.8 之前和其他语言，就不能这么写了，而是将 $-1$ 改成 $MOD - 2$。

为什么是 $MOD - 2$ 呢？因为 $x \times x^{MOD - 2} \equiv 1 \pmod{MOD}$，即 $x$ 的逆元就是 $x^{MOD - 2}$。

证明一下。

在 $MOD$ 的世界里，不算 $0$ 只有 $MOD - 1$ 个数字，记它们的所有数的乘积是 $s$ 。现在给所有数都乘上 $x$，于是有

两边都“除以” $s$，

也就是

好了，写代码了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
MOD = 1_000_000_007
MX = 100_000

# 组合数模板
# fac[i] i的阶乘
fac = [0] * MX
fac[0] = 1
for i in range(1, MX):
    fac[i] = fac[i - 1] * i % MOD

# inv_fac[i] i阶乘的逆元
inv_fac = [0] * MX
inv_fac[MX - 1] = pow(fac[MX - 1], -1, MOD)
for i in range(MX - 1, 0, -1):
    inv_fac[i - 1] = inv_fac[i] * i % MOD


# 计算组合数 C(n,k)
def comb(n: int, k: int) -> int:
    return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD


for i in range(1, 5):
    print(fac[i], inv_fac[i])
# 作者：灵茶山艾府
# 链接：https://leetcode.cn/problems/count-the-number-of-infection-sequences/solutions/2551734/zu-he-shu-xue-ti-by-endlesscheng-5fjp/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

更加通用的写法是，inv_fac[MX - 1] = pow(fac[MX - 1], MOD - 2, MOD)。

更进一步的，pow()背后做的就是快速幂，所以更通用的可以自己写快速幂。

更新

上面说「逆元」是在「模的世界」里才有，是不对的。根据豆包的解释，不同的代数系统都可以有逆元。

但我确实还是只站在「模的世界」出发，会好理解一些些逆元在算法中的作用。