组合计数
本节目标
从 Pascal 递推、阶乘逆元预处理到卡特兰数。
识别信号
“从若干位置选出若干个”“按前缀合法性排列 0/1”这类问题首先问：对象是否只关心选择集合或相对数量，而不关心选取顺序。小范围单次组合数适合递推；范围大且查询多时应预处理。
核心定义与不变量
组合数满足 Pascal 恒等式 C(a,b)=C(a-1,b-1)+C(a-1,b)，边界为 C(a,0)=C(a,a)=1。这给出按规模递推的计数方法。若改从全排列计数：a 个元素共有 a! 种排列，把前 b 个位置视为被选元素后，同一个 b 元子集会因选中部分内部的 b! 种顺序和未选部分的 (a-b)! 种顺序而被重复计数 b!(a-b)! 次，因此 C(a,b)=a!/(b!(a-b)!)。卡特兰数则计数所有长度 2n 的 0/1 序列中每个前缀都满足 0 的数量不少于 1 的数量。
朴素方法与瓶颈
递归展开 Pascal 三角会重复计算同一状态；每次直接求阶乘会重复预处理。枚举全部 2^(2n) 个 0/1 序列来筛合法前缀更会迅速失控。
推导与实现框架
小 a 时，直接沿 Pascal 恒等式预处理三角表。上界增大后，上一节的排列计数把递推结果压缩成阶乘公式；但模运算中不能直接做整数除法。本题模数是质数且所用阶乘均非零，所以预处理 fact[i] 与 invFact[i]，把分母除法改写为乘 fact[b] 和 fact[a-b] 的模逆元，即用 fact[a]·invFact[b]·invFact[a-b] 回答。卡特兰数再把组合数应用到路径模型：把 0 看作向右、1 看作向上，全部路径数减去首次越界路径数，即 C(2n,n)-C(2n,n-1)。
复杂度与数值边界
Pascal 预处理到上界 N 为 O(N²)；阶乘与逆阶乘预处理为 O(N)，每次查询 O(1)。卡特兰实现为 O(n + log MOD)。所有计数都在 1_000_000_007 下计算，减法后要规范化为非负余数。
母题序列
- 求组合数 I（必学）：Pascal 恒等式与小范围预处理。
- 求组合数 II（拓展）：阶乘、逆阶乘与批量查询。
- 满足条件的 01 序列（拓展）：前缀约束对应的卡特兰计数。
常见误区
不能把普通 / 放进取模公式；只有模数为质数且分母非零时才能用费马逆元。Pascal 递推的两端是 1，卡特兰的“越界路径”也必须从所有路径中减去并处理负模。
迁移方向
当组合数上界超过本题预处理范围或模数不再是质数，需要另一套工具；Lucas 定理、高精度组合数和完整容斥体系留给后续课程。