组合数与递推

10⁶ < p 这一句写得很刻意，理由在第 6 步会展开，先说结论：

只要 p ≤ n，n! 里就含有 p 这个因子 ⇒ n! ≡ 0 (mod p)，而 0 没有逆元。 整套公式当场失效，而且不报错、不崩溃，只是安静地给你一串 0。

⚠ 而 0 ≤ n, k ≤ 10⁶ 里那句「两个各自独立」同样刻意 —— 它意味着 k 可以大于 n。第 9 步会看到：顺手写的生成器永远造不出这种数据。

p = 999999937

 0 0   → 1        C(0,0) = 1
 5 0   → 1        ★ k = 0
 5 5   → 1        ★ k = n
 5 2   → 10
10 3   → 120
21 10  → 352716   ★ n = 21：21! 已经超过 long long
30 15  → 155117520
 3 7   → 0        ★★ k > n
25 25  → 1        ★ k = n
40 1   → 40
末行   → 1        （答案是 0 的只有一组）

四处特意安排，每一处都指着一个 bug：

• k = 0 和 k = n（三组）—— 那是「取全部 / 一个都不取」，用到的是 inv[0]；
• k > n（3 7）—— 题面规定答案是 0，而套公式会把 n−k 变成负数；
• n = 21 —— 21! ≈ 5.1×10¹⁹ 已经撞破 long long，阶乘那一行必须取模；
• p ≈ 10⁹ —— 三个 [0,p) 里的数连乘就是 10²⁷，中间必须取模。

从 n 个东西里挑 k 个，盯住第 n 个东西：

• 挑它 ⇒ 剩下的从前 n−1 个里挑 k−1 个 ⇒ C(n−1, k−1)；
• 不挑它 ⇒ 从前 n−1 个里挑 k 个 ⇒ C(n−1, k)。

两类不重不漏，加起来就是全部。∎

⚠ 注意它全程只有加法 —— 于是「取模」这件事在这里毫无难度（加完取一次就行）。 ★ 这一章所有的坑，都长在另一条路上（乘法和除法）。

C(n,k) = n! / (k! · (n−k)!)。可取模之下不能直接除 —— (a / b) mod p 和 (a mod p) / (b mod p) 根本不是一回事（6/3 = 2，可 6 mod 5 = 1、3 mod 5 = 3）。

★ 办法是把除法换成乘法：

b⁻¹ 是那个满足 b · b⁻¹ ≡ 1 (mod p) 的数，于是 a / b ≡ a · b⁻¹。

① 它什么时候存在？（第 40 章） b · x ≡ 1 (mod p) 就是 b·x + p·y = 1 有整数解 —— 按裴蜀定理，这等价于 gcd(b, p) = 1。 ⇒ p 是质数时，只要 b 不是 p 的倍数就一定有逆元。

② 怎么算？（第 41、42 章） 费马小定理：p 是质数、b 不是 p 的倍数 ⇒ b^(p−1) ≡ 1 ⇒ b⁻¹ ≡ b^(p−2)。 ⇒ 一次快速幂（第 42 章那五行）就够了。

⚠ 是 p−2，不是 p−1 —— 差一个数，b^(p−1) 算出来恒等于 1，整张表全废。

★ 数学这一块四章，到这里正好收口： 第 40 章给了「存不存在」，第 41 章给了「p 是质数」这个前提，第 42 章给了「怎么算」。

一个个求 (i!)⁻¹ 要 n 次快速幂（O(n log p)）。其实只要一次：

先求 (n!)⁻¹，然后 ((i−1)!)⁻¹ = (i!)⁻¹ · i      ← 从大往小倒着推

（因为 (i−1)! = i! / i，取逆元就是乘 i。）

点「运行 ▶」看结果

次数表（n = 10⁶，p = 10⁹+7，一次快速幂 45 次乘法）：

★ 那一句 ((i−1)!)⁻¹ = (i!)⁻¹ · i，把整整一个 log p 摊掉了。 （第 37 章自底向上建堆、第 38 章 O(n) 建树，都是同一种「把 log 摊掉」。）

⚠ 而三份代码的答案逐字节相同 —— 第 36 章那个「对拍看不见慢」的第八次现场。

点「运行 ▶」看结果

★★ 而 wrongInvEnd 那一条值得单看：它错的正好是 k ∈ {0,n} 那几组，别的一组不错 （check:viz 里钉着这条）。于是「k 取哪儿」这个旋钮有两头 —— 第 9 步会看到代价。

对着看档位 4 和档位 5：

k 专门塞 0 / n → wrongInvEnd 278；k 专门避开 0 / n → 62。

⚠ 而「避开」正是很多人会做的事 —— 觉得 k = 0 和 k = n 太平凡了，测不出什么。 ★ 可 wrongInvEnd 错的正好就是那几组。

① ⚠⚠ 档位 7 是一个很典型的陷阱：三条线全跨过去了，看着很完备 —— 可 wrongInvEnd 反而掉到 61。 因为「k 独立取」让 k 落在 [0, 60] 里，恰好等于 0 或 n 的概率反而变小了。

★ 补齐了几个边界，可能把另一个边界稀释掉 —— 又一次「某一支占得太多也是坑」（第 31 章）。

② 三个对照档说明三处改动各自不可替代**：撤掉哪一处，对应那一列就回到 0。**

第 17 章讲记忆化时说过：不带记忆的递归，调用次数正好排成杨辉三角。 说的是这个递归 —— 从 (0,0) 走到 (n,m)，每步只能往右或往下：

f(i, j) = f(i−1, j) + f(i, j−1)，边界 f(0,·) = f(·,0) = 1

它就是杨辉三角的递推（换了个方向摆），所以 f(n,m) = C(n+m, n)。

★ 那么「调用次数」是多少？设 g(i,j) = 求 f(n,m) 时 f(i,j) 被调用的次数。 只有 i,j 都 ≥ 1 的格子才会继续往下调（边界格直接返回 1）， 而这样的 f(i,j) 会被 f(i+1,j) 和 f(i,j+1) 各调用一次 —— 于是在那一片上 g 满足同一条递推，只是方向反过来：

g(i,j) = C((n−i)+(m−j), n−i)（i, j ≥ 1）

★★ 而边界格就是递归的叶子，每一片返回 1 ——

叶子的调用次数之和 = f(n,m) = C(n+m, n)，一个不多一个不少。

点「运行 ▶」看结果

n = m = 6 时：叶子加起来 924 次 = C(12,6)，总调用 1847 次。 把动画里的 n 拧到 7 看看那个总数 ——

⚠ 这就是第 17 章说的「不记忆化要重算多少遍」，而这一章给了它一个精确的数。