PYTHON LESSON 121
组合计数进阶：大数取模三大法宝
掌握组合数取模的三种方法（杨辉递推、阶乘+逆元、对称化简连乘），会根据数据范围选出最快的那种。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 阶乘表 fac[i] = fac[i - 1] * i % MOD 预处理
- 费马小定理求逆元 pow(x, MOD - 2, MOD)
- C(n, m) = fac[n] × inv(fac[m]) × inv(fac[n - m]) % MOD
01 · 核心概念
组合数对质数取模的三种算法与选型
组合数对质数取模的三种算法与选型：C(100, 50) 是一个 29 位的整数，C(10^6, 5×10^5) 更是天文数字，所以竞赛题几乎必带“对 10^9+7 取模”。Python 整数虽然不溢出，但随时取模能让中间结果始终很小、算得更快，也是和其他语言选手接轨的赛场习惯。
GESP Python 8 级 · 排列与组合（编程求解）GESP Python 8 级 · 倍增法（快速幂）大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
02 · 语法与规则
先记住这 3 条，再开始写程序
阶乘表 fac[i] = fac[i - 1] * i % MOD 预处理先准确读出这条写法的结构与作用。
费马小定理求逆元 pow(x, MOD - 2, MOD)换一组最小数据，手工推演一次结果。
C(n, m) = fac[n] × inv(fac[m]) × inv(fac[n - m]) % MOD再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 组合数取模三大法宝：同一个问题，三种武器
MOD = 10**9 + 7
# 法宝一：杨辉三角递推 O(n^2)，适合 n 较小（几千以内）
def comb_pascal(n, m):
tri = [[1] * (i + 1) for i in range(n + 1)]
for i in range(2, n + 1):
for j in range(1, i):
tri[i][j] = (tri[i - 1][j - 1] + tri[i - 1][j]) % MOD
return tri[n][m]
# 法宝二：阶乘 + 逆元 O(n)，n 到 10^6 都不怕
def comb_fact(n, m):
fac = [1] * (n + 1)
for i in range(1, n + 1):
fac[i] = fac[i - 1] * i % MOD
inv_m = pow(fac[m], MOD - 2, MOD) # 费马小定理求逆元
inv_nm = pow(fac[n - m], MOD - 2, MOD)
return fac[n] * inv_m % MOD * inv_nm % MOD
# 法宝三：对称化简 + 连乘，m 很小时最快
def comb_smart(n, m):
m = min(m, n - m) # C(n, m) == C(n, n-m)
ans = 1
for i in range(m):
ans = ans * (n - i) % MOD * pow(i + 1, MOD - 2, MOD) % MOD
return ans
print("C(10, 3) 三种方法:", comb_pascal(10, 3), comb_fact(10, 3), comb_smart(10, 3))
print("C(100, 50) mod 1e9+7 =", comb_fact(100, 50))
print("C(1000000, 500000) mod 1e9+7 =", comb_fact(1000000, 500000))
print("选型口诀：小 n 画三角，大 n 阶乘加逆元，小 m 直接连乘")C(10, 3) 三种方法: 120 120 120 C(100, 50) mod 1e9+7 = 538992043 C(1000000, 500000) mod 1e9+7 = 996692777 选型口诀：小 n 画三角，大 n 阶乘加逆元，小 m 直接连乘
三种方法算同一个 C(10, 3) 结果必须一致，这是最基本的自检；C(10^6, 5×10^5) 只有阶乘加逆元扛得住，运行约需两三秒。
04 · 逐步理解
每一步只解决一个问题
- 01
组合数为什么会爆炸
C(100, 50) 是一个 29 位的整数，C(10^6, 5×10^5) 更是天文数字，所以竞赛题几乎必带“对 10^9+7 取模”。Python 整数虽然不溢出，但随时取模能让中间结果始终很小、算得更快，也是和其他语言选手接轨的赛场习惯。
MOD = 10**9 + 7 - 02
法宝一：杨辉三角递推
边加边取模，每个数都不会超过 MOD。n 在几千以内时 O(n²) 完全够用，代码短、不易错；但 n 到 10^5 就要约 10^10 次加法，直接超时——数据范围先决定能不能用它。
tri[i][j] = (tri[i - 1][j - 1] + tri[i - 1][j]) % MOD - 03
法宝二：阶乘表 + 逆元
C(n, m) = n! ÷ (m! × (n−m)!)，模意义下不能做除法，要把“除以 x”换成“乘 x 的逆元”。先用 O(n) 循环预处理阶乘表 fac，再用两次 pow 求两个逆元，一次查询就拼出来了。
fac[n] * pow(fac[m], MOD - 2, MOD) % MOD - 04
逆元为什么成立：费马小定理
当 MOD 是质数且 x 不是 MOD 的倍数时，x^(MOD−1) ≡ 1 (mod MOD)，两边各除一个 x，得到 x 的逆元就是 x^(MOD−2)。10^9+7 是质数可不是巧合——题目选它就是为了让你能用这条定理。
inv = pow(x, MOD - 2, MOD) - 05
法宝三：对称化简 + 连乘
C(n, m) = C(n, n−m)，先把 m 化小再动手。m 只有几千时，m 次连乘、每步乘一个逆元反而最快，还省下了开阶乘表的内存。三个法宝不是背的，是按 n、m 的大小现场选的。
m = min(m, n - m) - 06
赛场选型口诀
小 n 画三角（递推稳），大 n 阶乘加逆元（预处理快），小 m 直接连乘（省内存）。如果一道题要查询很多次组合数，一定要先预处理阶乘表再回答，千万别每次重算——这是 TLE 与 AC 的分水岭。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行计算器，核对 C(10, 3) 三种方法都是 120
- 2比较三种方法各自适合的 n 范围
- 3说出为什么逆元要求模数是质数
- 4把 m 改成 n - m 验证对称化简结果不变
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法质数、约数、最大公因数与筛法建立整数整除体系，掌握试除、欧几里得算法、唯一分解和筛法的条件与复杂度。＋
正式定义
若整数 a 能被非零整数 b 整除，则 b 是 a 的约数。大于 1 且只有 1 和自身两个正约数的整数是质数；每个大于 1 的整数都能唯一分解为质数幂的乘积（忽略次序）。
必须掌握
- 0 和 1 都不是质数；判定 n 是否为质数只需试除到 floor(sqrt(n))。
- gcd(a,b)=gcd(b,a mod b) 构成欧几里得算法；lcm(a,b)=abs(a//gcd(a,b)*b) 并要处理 0。
- 约数成对出现，可枚举到平方根；完全平方数的平方根只计一次。
- 埃氏筛从 p² 开始标记质数 p 的倍数，总体 O(n log log n)；线性筛保证每个合数被最小质因子筛一次。
- 分解质因数后，约数个数与约数和可以由各质因数指数公式计算。
- 模运算支持加减乘分配；模除法不能直接用整数除法，需满足可逆条件并求逆元。
常见误区
- 把 1 判成质数
- 试除上界漏掉平方根
- 完全平方数的约数重复统计
- 取模后直接做普通除法
适用边界
- 大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
- 题目若涉及负数约数、0 的约数或模数非质数，必须先明确数学定义。
数学基础计数原理、组合数与计算几何基础明确有序/无序、互斥/分步与几何退化边界，再把公式转为稳定程序。＋
正式定义
加法原理用于互斥方案分类求和，乘法原理用于依次完成步骤求积；排列关心顺序，组合不关心顺序。计算几何用坐标、向量、距离和方向关系把图形条件转成数值判定。
必须掌握
- A(n,m)=n!/(n-m)!，C(n,m)=n!/(m!(n-m)!)，并有 C(n,m)=C(n,n-m)。
- 杨辉三角递推 C(n,m)=C(n-1,m-1)+C(n-1,m)，边界 C(n,0)=C(n,n)=1。
- 取模下的组合数算法取决于 n、模数是否为质数、查询次数和是否允许预处理。
- 距离比较应优先比较平方，避免不必要的 sqrt 和浮点误差。
- 三角形必须满足任意两边之和大于第三边；共线、重合、零长度是几何边界。
- 浮点比较应按题目误差使用容差；整数坐标能用叉积时优先保持整数计算。
常见误区
- 未判断顺序是否重要就套排列组合公式
- 模意义下直接做普通除法
- 浮点数直接用 ==
- 漏掉共线或退化图形
适用边界
- 概率需要在计数结果上再建立样本空间，不等同于组合数本身。
- 复杂计算几何涉及方向、相交、凸包等更多主题，本章只覆盖课程实际使用的基础判定。
Python 基础运算符、表达式与优先级完整区分算术、比较、逻辑、成员、身份和位运算，并用优先级表消除歧义。＋
正式定义
表达式求值得到一个值。运算符规定如何组合操作数；当一个表达式含多个运算符时，优先级和结合方向决定求值顺序，括号可以明确改变顺序。
必须掌握
- / 总是得到浮点结果；// 是向负无穷方向取整的整除；% 与 // 满足 a == (a // b) * b + a % b。
- 比较可以链式书写，如 0 <= x < 10；and/or 会短路并返回最后求值的操作数，不一定返回 bool。
- == 比较值是否相等，is 比较是否为同一个对象；判断 None 应写 is None。
- in/not in 做成员测试；对 dict 测试的是键。
- 位运算作用于整数的二进制位；负整数按无限长二进制补码语义理解。
- 复杂表达式即使能靠优先级正确运行，也应使用括号表达意图。
常见误区
- 把 // 当成简单截断
- 用 is 比较数字或字符串的值
- 忘记 and 的优先级高于 or
- 连续位移、比较和逻辑运算却不加括号
适用边界
- 浮点数比较受二进制表示误差影响，需要按问题选择容差。
- 运算符可由自定义类重载，因此相同符号对不同类型可能有不同语义。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
完成检查