第 6 章 · 03 线性代数/组合/概率（对应 docs/math/）

第 6 章 · 03 线性代数/组合/概率（对应 docs/math/）

本节定位：对应 OI Wiki docs/math/ 中除 number-theory、poly 之外的部分（线性代数、组合数学、概率论、博弈论等）。难度：进阶到高阶。前置依赖：第 6 章 · 01-02 节数论与多项式、第 5 章 DP（概率期望 DP 用到）。本节是非难点导读节，把零散的数学工具按"高频 → 进阶"串起来，矩阵快速幂和组合数是最高频考点。

⚠️ 注意：这些知识点相对独立，不像数论那样环环相扣，可以按需分块学。本节只导航，深入回 Wiki。

知识地图

一、线性代数（docs/math/linear-algebra/ 等）

• 矩阵运算（docs/math/linear-algebra/matrix.md）：加法、乘法、转置。乘法是 O(k³)（k 是阶数），这是所有矩阵算法复杂度的来源。矩阵乘法满足结合律但不满足交换律，这是矩阵快速幂可行的前提。
• ★ 矩阵快速幂（docs/math/linear-algebra/matrix.md）：把"线性递推"加速到 O(k³ log n)。经典例子斐波那契：构造转移矩阵 M，使 [f(n), f(n-1)]^T = M · [f(n-1), f(n-2)]^T，于是 [f(n), f(n-1)]^T = M^(n-1) · [f(1), f(0)]^T，用快速幂算 M^(n-1)。n 很大（如 10¹⁸）时只有矩阵快速幂能过。
• 高斯消元（docs/math/linear-algebra/gauss.md）：解线性方程组，O(n³)。通过初等行变换把增广矩阵化成上三角再回代。也用于求期望 DP 的方程组（列方程后高斯消元解）、求矩阵的秩。
• 线性基（docs/math/linear-algebra/basis.md）：异或空间的"极大线性无关组"，用于"选若干数使异或和最大""判断一个数能否被一组数异或得到"等问题。插入一个数 O(log 值域)，类似高斯消元但用二进制位。

💡 学习提示：矩阵快速幂是面试与竞赛双高频。任何"第 n 项由前 k 项线性组合"的递推，都能用矩阵快速幂 O(k³ log n) 解。务必会构造转移矩阵——把递推关系写成"状态向量 = 矩阵 × 旧状态向量"的形式。判断能否用矩阵快速幂，看"转移是否线性且系数固定"。

二、组合数学（docs/math/combinatorics/ 等）

• 排列组合：排列数 A(n,m)、组合数 C(n,m)。组合数用递推 C(n,m) = C(n-1,m-1) + C(n-1,m)（杨辉三角）或阶乘 + 逆元预处理（O(n) 预处理，O(1) 查询 C(n,m) = fact[n] · inv[m] · inv[n-m] mod p）。
• ★ 卢卡斯定理 Lucas（docs/math/number-theory/lucas.md）：求 C(n,m) mod p，当 n、m 远大于 p（p 为质数）时，Lucas 把它拆成 C(n mod p, m mod p) · C(n/p, m/p) mod p 递归。p 小（如 1e5）时必备，否则预处理表会爆空间。
• 卡特兰数 Catalan（docs/math/combinatorics/catalan.md）：括号匹配、出栈序列、二叉树计数、不相交路径等"计数问题"的通解。C_n = C(2n,n)/(n+1)，递推 C_n = Σ C_i · C_(n-1-i)。
• 容斥原理：|A1 ∪ A2| = |A1| + |A2| - |A1 ∩ A2|，推广到 n 个集合，符号交替。是计数问题的通用工具。

三、概率与期望（docs/math/probability/ 等）

• 概率期望 DP：期望有"线性性"——总期望 = 各部分期望之和，因此期望 DP 往往从终态倒推到起点。典型题：走到终点的期望步数、装备升级期望花费。状态定义通常是"从当前状态到终态的期望代价"。
• 期望的线性性是解题钥匙：把复杂期望拆成简单随机变量的期望之和（如"总操作次数 = 每个元素被操作次数之和"，分别算每个元素的期望被操作次数再相加）。即使随机变量不独立，线性性仍成立。

四、博弈论（docs/math/game-theory/ 等）

• ★ Nim 游戏（docs/math/game-theory/impartial-game.md）：n 堆石子轮流取，先手必胜 ⟺ 所有堆石子数的异或和 ≠ 0。
• SG 函数 Sprague-Grundy（docs/math/game-theory/impartial-game.md）：把任意"公平组合游戏"等价成 Nim，每个状态有个 SG 值，异或判定胜负。

四、博弈论（docs/math/game-theory/ 等）

• ★ Nim 游戏（docs/math/game-theory/impartial-game.md）：n 堆石子，两人轮流从某一堆取任意个，取到最后一个者胜。先手必胜 ⟺ 所有堆石子数的异或和 ≠ 0。这是组合博弈的基石结论。
• SG 函数 Sprague-Grundy（docs/math/game-theory/impartial-game.md）：把任意"公平组合游戏"（双方走法相同、信息完全公开、无随机）等价成 Nim——每个状态算一个 SG 值（mex 操作），游戏的 SG = 各子游戏 SG 的异或，非零则先手必胜。SG 函数把"千变万化的博弈"统一成"异或判定"。
• 非公平组合游戏 / 不平等博弈（如威佐夫博弈）：有专门的结论（如威佐夫博弈用黄金分割比），属进阶。

💡 学习提示：博弈论的套路很固定——判断是否"公平组合游戏"，若是就求 SG 异或判定。初学先彻底理解 Nim 结论（异或和判胜负），再学 SG 函数的 mex 定义，最后用 SG 解决"分石子游戏""阶梯 Nim"等变种。

各知识点的考查频率

学习建议

1. 最高频清单（优先学）：矩阵快速幂、组合数（含 Lucas）、Nim 博弈。这三个几乎每场比赛都可能出现，投入产出比最高。逆元已在第 6 章 · 01 节数论，默认掌握。
2. 进阶清单：高斯消元（期望 DP 配套）、线性基（异或问题）、卡特兰数、SG 函数、期望 DP。
3. 读 Wiki 顺序建议：linear-algebra/matrix.md（矩阵快速幂）→ combinatorics/（组合数）→ number-theory/lucas.md（Lucas）→ combinatorics/catalan.md（卡特兰）→ probability/（期望 DP）→ game-theory/（Nim/SG）→ linear-algebra/gauss.md（高斯消元）→ linear-algebra/basis.md（线性基）。
4. 矩阵快速幂的学法：先用斐波那契（k=2）手算构造转移矩阵，再推广到 k 项递推。关键是"状态向量 + 转移矩阵"的拆分——把递推的每一项写成矩阵乘法。
5. 组合数预处理：比赛里 C(n,m) 几乎都要 mod p，预处理阶乘 + 逆元是标准套路（O(n) 预处理，O(1) 查询）。n 很大、p 很小（≤ 1e6）时改用 Lucas。
6. 期望 DP 的学法：牢记"期望 DP 一般从终态倒推"，且善用"期望的线性性"拆分复杂期望。很多期望题的难点不在 DP 本身，而在用线性性把问题拆开。

💡 学习提示：这一节的知识点是"工具箱式"的，不必一次学完。建议按题目驱动：刷到哪类题就学哪个工具。矩阵快速幂和组合数是底层，优先打底；期望 DP 和博弈论是专题，集中突破。

本节要点

• 矩阵快速幂：线性递推加速到 O(k³ log n)，斐波那契是经典例，务必会构造转移矩阵。
• 高斯消元：解线性方程组 O(n³)，期望 DP 常配套；线性基解"异或和最大"问题。
• 组合数 + 卢卡斯定理 Lucas：n、m 大于模数 p 时求 C(n,m) mod p；卡特兰数解括号/出栈/二叉树计数。
• 概率期望 DP：用期望线性性从终态倒推，复杂期望拆成简单期望之和。
• 博弈论：Nim 异或和判定 + SG 函数（mex + 异或），公平组合游戏的通用解法。
• 优先学矩阵快速幂和组合数；深入见 docs/math/ 各子目录。