PYTHON LESSON 123
例题精练：网格路径计数四步通关
按“读题→建模→编码→验证”四步完整拆解一道八级计数编程题，并掌握小数据对拍的验证习惯。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 共走 n+m-2 步、选 n-1 步向下：C(n+m-2, n-1)
- 阶乘表 + pow(x, MOD - 2, MOD) 逆元取模
- 小数据用 DP 对拍验证公式正确性
01 · 核心概念
组合数 + 逆元解决大数据计数的完整流程
组合数 + 逆元解决大数据计数的完整流程：机器人从左上到右下，每步只能向右或向下，问走法数并对 10^9+7 取模。先圈出 n、m ≤ 10^6：DP 是 O(nm) = 10^12 次运算，必超时。结论立刻清晰——这题必须找数学公式。
GESP Python 8 级 · 排列与组合（编程求解）GESP Python 8 级 · 时间与空间复杂度分析大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
02 · 语法与规则
先记住这 3 条，再开始写程序
共走 n+m-2 步、选 n-1 步向下：C(n+m-2, n-1)先准确读出这条写法的结构与作用。
阶乘表 + pow(x, MOD - 2, MOD) 逆元取模换一组最小数据，手工推演一次结果。
小数据用 DP 对拍验证公式正确性再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 例题精练：网格路径计数（题库 py-grid-paths 同款）
# 读题 → 建模 → 编码 → 验证，四步走完一道八级计数题
def by_formula(n, m):
"""公式法：走法数 = C(n+m-2, n-1)，阶乘表 + 逆元取模"""
MOD = 10**9 + 7
N, K = n + m - 2, n - 1
fac = [1] * (N + 1)
for i in range(1, N + 1):
fac[i] = fac[i - 1] * i % MOD
return fac[N] * pow(fac[K], MOD - 2, MOD) % MOD * pow(fac[N - K], MOD - 2, MOD) % MOD
def by_dp(n, m):
"""暴力 DP（只用于小数据验证）：f[i][j] = f[i-1][j] + f[i][j-1]"""
f = [[1] * m for _ in range(n)]
for i in range(1, n):
for j in range(1, m):
f[i][j] = f[i - 1][j] + f[i][j - 1]
return f[n - 1][m - 1]
# 小数据对拍：两种方法答案必须一致
for n, m in [(3, 3), (4, 5), (10, 10)]:
print(f"{n}x{m} 网格: 公式={by_formula(n, m)} DP={by_dp(n, m)}")
# 大数据：DP 算不动，公式法轻松拿下
print("1000000x1000000 网格:", by_formula(10**6, 10**6))3x3 网格: 公式=6 DP=6 4x5 网格: 公式=35 DP=35 10x10 网格: 公式=48620 DP=48620 1000000x1000000 网格: 541097174
最后一行要预处理约 200 万项的阶乘表，运行约两三秒属正常；三组小数据两种方法结果一致，公式才可信。
04 · 逐步理解
每一步只解决一个问题
- 01
第一步：读题，先圈数据范围
机器人从左上到右下，每步只能向右或向下，问走法数并对 10^9+7 取模。先圈出 n、m ≤ 10^6：DP 是 O(nm) = 10^12 次运算，必超时。结论立刻清晰——这题必须找数学公式。
# n, m ≤ 10^6 → DP O(nm) 超时，必须公式 O(n) - 02
第二步：建模成组合数
无论怎么走，总共要走 (n−1) 步向下和 (m−1) 步向右，共 n+m−2 步。只要从中选定哪 n−1 步向下，整条路径就唯一确定了。所以走法数 = C(n+m−2, n−1)——一行式子，题目从“路径问题”变成“组合数计算”。
answer = C(n + m - 2, n - 1) - 03
第三步：编码，阶乘表 + 逆元
预处理阶乘表到 N = n+m−2（最大约 2×10^6，列表要开够），再用两次 pow 求逆元拼出组合数。这套写法就是 121 课的法宝二，直接搬过来用——学算法要学到“即插即用”的熟练度。
fac[N] * pow(fac[K], MOD - 2, MOD) % MOD * pow(fac[N - K], MOD - 2, MOD) % MOD - 04
第四步：验证，小数据对拍
公式推得快，但可能推错；DP 慢，却直观可靠。聪明的做法是两个都写：用 DP 在小数据上当“标准答案”，和公式法逐一比对。3x3、4x5、10x10 三组全一致，才敢交大数据——这个习惯叫“对拍”，是竞赛选手的保命符。
for n, m in [(3, 3), (4, 5), (10, 10)]: assert by_formula(n, m) == by_dp(n, m) - 05
算一笔性能账
公式法在 10^6 × 10^6 时预处理 200 万项阶乘表，几秒钟出答案；而 DP 要开 10^12 个格子，内存先爆炸。同一道题，算法差一个量级就是“秒出”与“跑不完”的区别。
- 06
变体预告：带障碍的网格
如果网格里有格子禁止通行，纯组合数就失效了，要回到 DP 递推：f[i][j] = (f[i−1][j] + f[i][j−1]) % MOD，障碍格直接置 0。记住选型原则：能公式则公式，有障碍则递推。
if blocked[i][j]: f[i][j] = 0
05 · 练习与检验
自己写出来，才算真正学会
- 1运行拆解室，核对 3x3 两种方法都是 6
- 2读题先圈数据范围 10^6，判断纯 DP 不可行
- 3手推 2x2 网格验证公式 C(2, 1) = 2
- 4说出“对拍”为什么比肉眼检查靠谱
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 的约数或模数非质数，必须先明确数学定义。
Python 基础运算符、表达式与优先级完整区分算术、比较、逻辑、成员、身份和位运算，并用优先级表消除歧义。＋
正式定义
表达式求值得到一个值。运算符规定如何组合操作数；当一个表达式含多个运算符时，优先级和结合方向决定求值顺序，括号可以明确改变顺序。
必须掌握
- / 总是得到浮点结果；// 是向负无穷方向取整的整除；% 与 // 满足 a == (a // b) * b + a % b。
- 比较可以链式书写，如 0 <= x < 10；and/or 会短路并返回最后求值的操作数，不一定返回 bool。
- == 比较值是否相等，is 比较是否为同一个对象；判断 None 应写 is None。
- in/not in 做成员测试；对 dict 测试的是键。
- 位运算作用于整数的二进制位；负整数按无限长二进制补码语义理解。
- 复杂表达式即使能靠优先级正确运行，也应使用括号表达意图。
常见误区
- 把 // 当成简单截断
- 用 is 比较数字或字符串的值
- 忘记 and 的优先级高于 or
- 连续位移、比较和逻辑运算却不加括号
适用边界
- 浮点数比较受二进制表示误差影响，需要按问题选择容差。
- 运算符可由自定义类重载，因此相同符号对不同类型可能有不同语义。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
数学基础计数原理、组合数与计算几何基础明确有序/无序、互斥/分步与几何退化边界，再把公式转为稳定程序。＋
正式定义
加法原理用于互斥方案分类求和，乘法原理用于依次完成步骤求积；排列关心顺序，组合不关心顺序。计算几何用坐标、向量、距离和方向关系把图形条件转成数值判定。
必须掌握
- 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 和浮点误差。
- 三角形必须满足任意两边之和大于第三边；共线、重合、零长度是几何边界。
- 浮点比较应按题目误差使用容差；整数坐标能用叉积时优先保持整数计算。
常见误区
- 未判断顺序是否重要就套排列组合公式
- 模意义下直接做普通除法
- 浮点数直接用 ==
- 漏掉共线或退化图形
适用边界
- 概率需要在计数结果上再建立样本空间，不等同于组合数本身。
- 复杂计算几何涉及方向、相交、凸包等更多主题，本章只覆盖课程实际使用的基础判定。
完成检查