数学 · 组合数与帕斯卡三角

1. 核心原理

组合数学要解决的问题模板长这样："给一个集合 / 步骤序列 / 排列空间，数出满足约束的方案数"——不同路径、不同播放列表、不同放球方式，骨架都是同一套计数。和"求一个最优值"的 DP / 贪心明显不一样：组合题一定要把所有合法方案都数清楚，多一个少一个都算错。

一类核心计数对象是二项系数 C(n, k)——表示从 n 个不同元素里挑 k 个的方法数（不计顺序）。它满足两条核心恒等式：

• 定义式：C(n, k) = n! / (k! · (n - k)!)
• Pascal 递推：C(n, k) = C(n - 1, k - 1) + C(n - 1, k)

边界：C(n, 0) = C(n, n) = 1；C(n, k) = 0 当 k < 0 或 k > n。

为什么有些 DP 题其实有组合闭式

很多网格 / 步骤计数题表面是 DP，本质是组合数。LC 62 不同路径就是典型：从 (0, 0) 走到 (m - 1, n - 1)，无论怎么走都要往下 m - 1 步、往右 n - 1 步，总共 m + n - 2 步。一条路径就是这些步的一个排列，唯一的自由度是"在 m + n - 2 步里选哪 m - 1 步是往下"，答案就是 C(m + n - 2, m - 1)。

设 f[i][j] 表示从 (0, 0) 走到 (i, j) 的路径数，转移 f[i][j] = f[i - 1][j] + f[i][j - 1]，第一行第一列全为 1。这条递推的"形状"和 Pascal 递推 C(n, k) = C(n - 1, k - 1) + C(n - 1, k) 同构——把 f[i][j] 旋转一下就是 C(i + j, i)。m = 3, n = 7 时 f[2][6] = C(8, 2) = 28。

LC 62 的 DP 表 (m = 3, n = 7)
        j=0  j=1  j=2  j=3  j=4  j=5  j=6
i = 0     1    1    1    1    1    1    1
i = 1     1    2    3    4    5    6    7
i = 2     1    3    6   10   15   21   28 ←  = C(8, 2)

DP 解法是 O(mn) 时间 + O(n) 空间（滚动）；组合数解法是 O(min(m, n)) 时间 + O(1) 空间（边乘边除）。当查询次数多（反复算不同的 m, n）时，预处理阶乘和阶乘逆元后每次 O(1)。

何时组合数闭式失效：网格上一个不规则障碍（LC 63）就让"所有路径等价于排列"这个对称性破坏，必须回 DP。原则是：步数固定、只看分配方式时用组合数；带不规则障碍 / 代价 / 顺序约束时用 DP。

Pascal 递推与杨辉三角

把 Pascal 递推画出来就是杨辉三角：

n=0:           1
n=1:          1 1
n=2:         1 2 1
n=3:        1 3 3 1
n=4:       1 4 6 4 1
n=5:      1 5 10 10 5 1
n=6:    1 6 15 20 15 6 1

第 n 行的第 k 个数就是 C(n, k)。每个非边缘数等于正上方两个数之和：C(4, 2) = C(3, 1) + C(3, 2) = 3 + 3 = 6。两边的 1 对应 C(n, 0) = C(n, n) = 1 边界。优点是没有除法——只有加法，对任意模数都安全。缺点是空间 O(n²)，n 大就吃不消。LC 118 直接构造这张表的前 numRows 行。

阶乘 + 模逆元

n 较大（比如 10⁶）时建不动 O(n²) 的 Pascal 表。换思路：把分子分母分别预处理——fact[i] = i! mod p，inv_fact[i] = (i!)⁻¹ mod p，查询时：

C(n, k) = fact[n] · inv_fact[k] · inv_fact[n - k]   (mod p)

预处理 O(n)，单次查询 O(1)。模数必须是质数（费马小定理要求 gcd(a, p) = 1，质数自动满足），常用 10⁹ + 7 / 998244353。

fact[N] 的逆元用费马小定理 a⁻¹ ≡ a^(p − 2) (mod p)：对 fact[N] 做一次快速幂，复杂度 O(log p)。其余 inv_fact[i] 倒着递推：

inv_fact[i - 1] = inv_fact[i] · i mod p

理由是 inv_fact[i - 1] = 1 / (i - 1)! = (1 / i!) · i = inv_fact[i] · i。倒推一次扫完，整体预处理仍是 O(n) 而非 O(n log p)。

三条主路线的选择

LC 920 / LC 1359 / LC 2400 都属于"大数据范围下反复算组合数取模"的场景，走阶乘 + 逆元路线。

2. 通用模板

下面给两套核心模板：Pascal 递推表（模数任意，O(n²) 预处理）和阶乘 + 模逆元（模数质数，O(n) 预处理）。两套都是三语言完整版。

模板 A：Pascal 递推表

tbl[i][j] = C(i, j) mod MOD，MOD = 10⁹ + 7。建表后查询 C(n, k) 直接读 tbl[n][k]。

MOD = 10**9 + 7

def pascal_table(N: int) -> list[list[int]]:
    tbl = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        tbl[i][0] = 1
        for j in range(1, i + 1):
            tbl[i][j] = (tbl[i - 1][j - 1] + tbl[i - 1][j]) % MOD
    return tbl

class Combo {
    static final int MOD = 1_000_000_007;
    long[][] tbl;

    Combo(int N) {
        tbl = new long[N + 1][N + 1];
        for (int i = 0; i <= N; i++) {
            tbl[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                tbl[i][j] = (tbl[i - 1][j - 1] + tbl[i - 1][j]) % MOD;
            }
        }
    }

    long C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return tbl[n][k];
    }
}

class Combo {
public:
    static constexpr long long MOD = 1000000007LL;
    vector<vector<long long>> tbl;

    Combo(int N) : tbl(N + 1, vector<long long>(N + 1, 0)) {
        for (int i = 0; i <= N; i++) {
            tbl[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                tbl[i][j] = (tbl[i - 1][j - 1] + tbl[i - 1][j]) % MOD;
            }
        }
    }

    long long C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return tbl[n][k];
    }
};

时间空间 O(N²)。N = 5000 时大约 2.5 × 10⁷ 次加法、200 MB 内存（long 数组）。

模板 B：阶乘 + 模逆元

MOD = 10**9 + 7

class Combo:
    def __init__(self, N: int):
        # fact 正推：fact[i] = i!
        self.fact = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fact[i] = self.fact[i - 1] * i % MOD
        # inv_fact 倒推：仅对 fact[N] 做一次快速幂，其余靠 inv_fact[i-1] = inv_fact[i] * i
        self.inv_fact = [1] * (N + 1)
        self.inv_fact[N] = pow(self.fact[N], MOD - 2, MOD)
        for i in range(N - 1, -1, -1):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD

    def C(self, n: int, k: int) -> int:
        if k < 0 or k > n or n < 0:
            return 0
        return self.fact[n] * self.inv_fact[k] % MOD * self.inv_fact[n - k] % MOD

class Combo {
    static final int MOD = 1_000_000_007;
    long[] fact, invFact;

    Combo(int N) {
        fact = new long[N + 1];
        invFact = new long[N + 1];
        fact[0] = 1;
        for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
        invFact[N] = pow(fact[N], MOD - 2);            // 一次快速幂
        for (int i = N - 1; i >= 0; i--) {
            invFact[i] = invFact[i + 1] * (i + 1) % MOD;   // 倒推一次扫完
        }
    }

    long C(int n, int k) {
        if (k < 0 || k > n || n < 0) return 0;
        return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
    }

    private long pow(long a, long b) {
        long res = 1;
        a %= MOD;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
}

class Combo {
    static constexpr long long MOD = 1000000007LL;
    vector<long long> fact, invFact;

    long long qpow(long long a, long long b) {
        long long res = 1;
        a %= MOD;
        while (b > 0) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }

public:
    Combo(int N) : fact(N + 1, 1), invFact(N + 1, 1) {
        for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
        invFact[N] = qpow(fact[N], MOD - 2);                // 一次快速幂
        for (int i = N - 1; i >= 0; i--) {
            invFact[i] = invFact[i + 1] * (i + 1) % MOD;    // 倒推一次扫完
        }
    }

    long long C(int n, int k) {
        if (k < 0 || k > n || n < 0) return 0;
        return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
    }
};

预处理 O(N)，每次 C(n, k) 查询 O(1)。几点要说明：

• inv_fact 必须倒推。如果正着推 inv_fact[i] = inv_fact[i - 1] / i，又要除法，没快。
• 每步乘完立即 mod。fact[n] · inv_fact[k] 两个 < MOD 的数相乘最大约 10¹⁸，刚好在 int64 范围内。绝不要"乘三个再 mod"——(10⁹)³ ≈ 10²⁷ 必爆 long。
• 越界保护。模板里 if k < 0 or k > n or n < 0: return 0 一定要写——LC 2400 算"走 k 步净位移 d"时 (k + d) / 2 可能不在 [0, k] 范围，没这行直接数组越界。
• 单次小查询不用预处理。LC 62 这种"算一次组合数"的场景直接 O(min(m, n)) 边乘边除即可（见 §4.1 Java 版），不需要开 10⁶ 大小的 fact 数组。

3. 母题精讲

LeetCode 62. Unique Paths

链接：LeetCode 62

题目（中文翻译）：一个机器人位于 m × n 网格的左上角 (0, 0)，目标是右下角 (m - 1, n - 1)。每一步只能往右或往下走一格。返回从起点到终点的不同路径总数。

数据范围：

• m, n：1 到 100
• 题目保证答案不超过 2 × 10⁹

示例：

输入：m = 3, n = 7
输出：28

输入：m = 3, n = 2
输出：3
解释：三条路径分别是
  右 → 下 → 下
  下 → 右 → 下
  下 → 下 → 右

解法一：网格 DP

设 f[i][j] 表示从 (0, 0) 走到 (i, j) 的路径数。一格只能从正上方或正左方过来：

f[i][j] = f[i - 1][j] + f[i][j - 1]

边界是第一行第一列全为 1。最终答案是 f[m - 1][n - 1]。

class Solution:
    def uniquePaths_dp(self, m: int, n: int) -> int:
        f = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                f[i][j] = f[i - 1][j] + f[i][j - 1]
        return f[m - 1][n - 1]

时间 O(mn)，空间 O(mn)。空间能滚到 O(n)（只保留一行），但时间仍是 O(mn)。

解法二：组合数闭式 C(m + n - 2, m - 1)

按 §1 的推导，从 (0, 0) 走到 (m - 1, n - 1) 共 m + n - 2 步，唯一自由度是"在这 m + n - 2 步里选哪 m - 1 步是往下"——答案就是 C(m + n - 2, m - 1)。m = 3, n = 7 时 C(8, 2) = 28，与 DP 表的右下角完全一致。

闭式解时间 O(min(m, n))、空间 O(1)，比 DP 快一档。两种解法的对照走完之后，§4.1 重新给完整代码（含 Java 边乘边除版避免溢出）。

4. 例题（三道）

按"DP vs 组合数闭式"对照排：先看 LC 62 双解、再看带障碍版必须 DP、最后看 LC 118 直接产出组合数表。

4.1 LC 62 不同路径

回到本章开头那道题。两种解法都给出来对照——同一个答案，复杂度差一个数量级。

class Solution:
    # 解法一：网格 DP
    def uniquePaths_dp(self, m: int, n: int) -> int:
        f = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                f[i][j] = f[i - 1][j] + f[i][j - 1]
        return f[m - 1][n - 1]

    # 解法二：组合数 C(m + n - 2, m - 1)
    def uniquePaths(self, m: int, n: int) -> int:
        # 答案题目保证 ≤ 2 × 10⁹，可以用 Python 的大整数直接算
        # 不取模时直接乘除：C(N, K) = N! / (K! · (N - K)!)
        from math import comb
        return comb(m + n - 2, m - 1)

DP 解法时间空间 O(mn)。组合数解法时间 O(min(m, n))（Python math.comb 内部实现），空间 O(1)。

为什么数据范围 m, n ≤ 100 时两种都能过？因为 C(198, 99) ≈ 9 × 10⁵⁸ 早就爆了 64-bit 整数。但题目特别说明"答案不超过 2 × 10⁹"——这是 32-bit 有符号整数上限附近，意思是测试用例里不会真的让你算 C(198, 99)。Python 用 math.comb 自动大整数没问题；Java / C++ 用 long 也够（最大 2 × 10⁹ < 2⁶³）。

class Solution {
    public int uniquePaths(int m, int n) {
        // C(m + n - 2, m - 1)，用 long 避免乘法溢出
        long ans = 1;
        int N = m + n - 2;
        int K = Math.min(m - 1, n - 1);            // 取较小者，少算几步
        for (int i = 1; i <= K; i++) {
            ans = ans * (N - K + i) / i;           // 边乘边除，保持整除
        }
        return (int) ans;
    }
}

Java 这版用"边乘边除"避免提前算出 N! 爆 long。关键是 ans * (N - K + i) 一定能被 i 整除（因为前 i 步累计是 C(N - K + i, i) 必是整数）。把 K 取成 min(m - 1, n - 1) 让乘除次数减半。

Follow-up：如果网格上有障碍格（不能走的位置），还能用组合数吗？

4.2 LC 63 不同路径 II

链接：LeetCode 63

题意：跟 LC 62 同样的网格，但加了障碍——obstacleGrid[i][j] == 1 表示该格不能走。求从左上到右下的路径数。

数据范围：

• m, n：1 到 100
• obstacleGrid[i][j]：0 或 1
• 答案题目保证不超过 2 × 10⁹

示例：

输入：obstacleGrid = [
  [0, 0, 0],
  [0, 1, 0],
  [0, 0, 0]
]
输出：2
解释：3 × 3 网格中间格 (1, 1) 是障碍，绕过它有两条路。

带障碍后组合数闭式解就用不上了——障碍破坏了"所有路径等价于排列"这个对称性。回到 DP：

f[i][j] = 0                              如果 obstacleGrid[i][j] == 1
f[i][j] = f[i - 1][j] + f[i][j - 1]      其他

边界：第一行第一列上，一旦遇到障碍，后面的格子都到不了，f 全是 0。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        if obstacleGrid[0][0] == 1:                # 起点就是障碍，直接 0
            return 0
        f = [[0] * n for _ in range(m)]
        f[0][0] = 1
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    f[i][j] = 0
                    continue
                if i > 0:
                    f[i][j] += f[i - 1][j]
                if j > 0:
                    f[i][j] += f[i][j - 1]
        return f[m - 1][n - 1]

时间 O(mn)，空间 O(mn)。

空间优化到 O(n)：观察 f[i][j] 只依赖于 f[i - 1][j]（上方）和 f[i][j - 1]（同行左边）。用一维数组滚一遍：

class Solution:
    def uniquePathsWithObstacles_O1(self, obstacleGrid: list[list[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        f = [0] * n
        f[0] = 1 if obstacleGrid[0][0] == 0 else 0
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    f[j] = 0
                elif j > 0:
                    f[j] += f[j - 1]               # f[j] 此时是上一行的 f[i-1][j]
        return f[n - 1]

空间 O(n)。f[j] += f[j - 1] 这一行同时完成了"读 f[i - 1][j]（旧 f[j]）"和"加 f[i][j - 1]（已更新的 f[j - 1]）"。

这道题专门为了对照 LC 62 而出——网格上一个不规则障碍就让组合数闭式失效，必须老老实实 DP。组合数适用于"对称、无障碍"的格点问题；一旦带不规则限制（障碍 / 不同代价），就要用 DP。

Follow-up：如果不要算路径数、而要直接构造前 n 行所有 C(i, j) 的值——也就是杨辉三角呢？

4.3 LC 118 杨辉三角

链接：LeetCode 118

题意：给一个非负整数 numRows，返回杨辉三角的前 numRows 行。每行的每个元素是上一行相邻两元素之和（两端是 1）。

数据范围：

• 1 ≤ numRows ≤ 30
• 题目保证元素不溢出

示例：

输入：numRows = 5
输出：[
  [1],
  [1, 1],
  [1, 2, 1],
  [1, 3, 3, 1],
  [1, 4, 6, 4, 1]
]

杨辉三角的第 i 行第 j 个元素就是 C(i, j)。直接按 C(i, j) = C(i - 1, j - 1) + C(i - 1, j) 递推：

class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        triangle = []
        for i in range(numRows):
            row = [1] * (i + 1)                    # 两端先填 1
            for j in range(1, i):
                row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
            triangle.append(row)
        return triangle

时间 O(numRows²)，空间 O(numRows²)（输出本身就这么大，不算额外空间则 O(1)）。

工程上有个小技巧：row = [1] * (i + 1) 先把两端的 1 填好，只需循环 j ∈ [1, i) 填中间，省掉 j == 0 和 j == i 的边界判断。i == 0 或 i == 1 时内层循环不执行，自动得到 [1] 和 [1, 1]。Java / Go 写法同款，先 Arrays.fill(row, 1) 再覆盖中间。

如果只要某一行而不要整张表，参考 6.1 LC 119（空间 O(rowIndex)）。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) row.add(1);
            for (int j = 1; j < i; j++) {
                row.set(j, ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
            }
            ans.add(row);
        }
        return ans;
    }
}

这道题是组合数 Pascal 表的最直接产物——把第 3 节的 tbl[i][j] = tbl[i - 1][j - 1] + tbl[i - 1][j] 原样搬过来即可（去掉 mod，因为 numRows ≤ 30 不溢出）。

5. 边界、易错与复杂度

模数为质数 vs 任意模数

阶乘 + 逆元只在模数 p 是质数时有效（费马小定理要 gcd(a, p) = 1，质数自动满足）。常见质数：10⁹ + 7、10⁹ + 9、998244353。

模数不是质数（比如题目要 mod 一个合数 m）时只能用 Pascal 递推——它只做加法、不做除法，对任意模数都正确。代价是 O(n²) 空间，n > 5000 就够呛。

边界值

C(n, 0) = C(n, n) = 1
C(n, k) = 0    如果 k < 0 或 k > n
C(0, 0) = 1

模板里的 if k < 0 or k > n or n < 0: return 0 一定要写——LC 2400 算"走 k 步净位移 abs 的方法数"时 (k + abs) / 2 可能不在 [0, k] 范围内，没这行保护直接数组越界。

阶乘逆元的预处理顺序

正向递推（fact[0] → fact[N]）是 fact[i] = fact[i - 1] · i。

逆元必须倒着递推（inv_fact[N] → inv_fact[0]）：

inv_fact[N] = pow(fact[N], MOD - 2, MOD)      # 一次快速幂
inv_fact[i - 1] = inv_fact[i] · i mod MOD     # 倒推

为什么倒推？因为 inv_fact[i - 1] = 1 / (i - 1)! = (1 / i!) · i = inv_fact[i] · i。如果正着推 inv_fact[i] = inv_fact[i - 1] / i，又要除法，没快。

整数溢出

fact[i] · inv_fact[k] 两个 < MOD 的数相乘最大约 (10⁹)² = 10¹⁸，刚好在 int64 (< 9.2 × 10¹⁸) 范围内。所以两两相乘后立即 mod 一次，绝不要"乘三个再 mod"——(10⁹)³ ≈ 10²⁷ 必爆 long。

# 对：每次乘完立即 mod
return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

# 错：三个乘一起再 mod，C/Java 中会溢出
return (fact[n] * inv_fact[k] * inv_fact[n - k]) % MOD

Python 因为大整数不会真溢出，但中间值变大会拖慢——也建议每步都 mod。

O(1) 单次查询 vs O(min(m, n)) 直接乘

LC 62 这种"算一次组合数"的场景，不需要预处理整张阶乘表——直接 O(min(m, n)) 边乘边除即可（见 4.1 Java 版）。开 10⁶ 大小的 fact 数组反而浪费内存。判断标准：单次查询且 n 小就直接边乘边除；多次查询、n ≤ 10⁶、质数模数就预处理 fact + inv_fact；模数任意或 n ≤ 5000 退回 Pascal 表。

复杂度速查

7. 小结

这一章把"DP vs 组合数闭式"对照看了一遍。掌握三件事就能把组合数用好：

• 识别闭式：当问题有"步数固定、只看分配方式"的结构（LC 62、LC 2400），优先想组合数；带不规则障碍 / 代价时回 DP（LC 63）。
• 选对算法：模数任意 / n ≤ 5000 用 Pascal，模数质数 / n ≤ 10⁶ 用阶乘 + 逆元，单次小查询直接边乘边除。
• 逆元的工程套路：fact 正推、inv_fact 倒推，只对 fact[N] 做一次快速幂——这是预处理 O(N) 而不是 O(N log MOD) 的关键。

数学章下一节进入概率与期望——把"方案数 / 总方案数"扩展到带权重的随机过程，常见于强化学习类面试题（LC 808 分汤、LC 837 21 点）。

对应灵神题单：数学算法 · 组合数学

进一步阅读：灵茶山艾府《组合数学题单》；LeetCode Math 标签 与 Combinatorics 标签 高频题