【GESP】C++八级考试大纲知识点梳理 (3) 杨辉三角与组合数

继上一篇我们探讨了排列和组合之后，GESP C++八级大纲的第三条考点非常经典，它是计算机算法（尤其是动态规划）的重要入门案例。

（3）掌握杨辉三角形（又称帕斯卡三角形）的概念。

杨辉三角形（Yang Hui’s Triangle），在西方称为帕斯卡三角形（Pascal’s Triangle），是一个无限对称的数字三角形。它不仅在形式上优美，更蕴含了深厚的组合数学原理。

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。

一、杨辉三角的概念与构造

杨辉三角的构造规则非常简单，概括为一句话：每个数等于它上方两数之和。

1.1 形状演示

如果我们把三角形写出来，前几行是这样的：

Row 0:      1
Row 1:     1 1
Row 2:    1 2 1
Row 3:   1 3 3 1
Row 4:  1 4 6 4 1
...

或者用左对齐的方式（在计算机二维数组中更常见）：

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

1.2 递推公式

如果用 $tri[i][j]$ 表示第 $i$ 行第 $j$ 列的数字（行列索引从 0 开始），那么有：

1. 边界条件：每一行的第一个数和最后一个数都是 1。 \(tri[i][0] = 1, \quad tri[i][i] = 1\)
2. 递推关系：中间的数等于它正上方 ($i-1, j$) 和左上方 ($i-1, j-1$) 的数之和。 \(tri[i][j] = tri[i-1][j-1] + tri[i-1][j]\)

这其实就是我们上一章提到的组合数公式 $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$ 的完美图形化体现。

---

二、杨辉三角与组合数的关系

杨辉三角最核心的数学意义在于：第 $n$ 行的第 $m$ 个数，恰好就等于组合数 $C_n^m$ （即 $\binom{n}{m}$）。

注意：这里的行号 $n$ 和列号 $m$ 都是从 0 开始计数的。

2.1 验证

• 第 2 行：1, 2, 1
  • $C_2^0 = 1$
  • $C_2^1 = 2$
  • $C_2^2 = 1$
• 第 3 行：1, 3, 3, 1
  • $C_3^0 = 1$
  • $C_3^1 = 3$
  • $C_3^2 = 3$
  • $C_3^3 = 1$
• 第 4 行：1, 4, 6, 4, 1
  • $C_4^2 = \frac{4 \times 3}{2 \times 1} = 6$，确实对应第 4 行第 2 列的 6。

2.2 为什么会有这个关系？

这就回到了组合数的定义。 假设我们要在 $n$ 个物品中选 $m$ 个（$C_n^m$）： 我们可以把这 $n$ 个物品中的某一个特定物品（比如“特殊的红球”）单独拿出来看。 选出的 $m$ 个物品中，只有两种情况：

1. 包含这个红球：那么还需要从剩下的 $n-1$ 个中选 $m-1$ 个。即 $C_{n-1}^{m-1}$。
2. 不包含这个红球：那么需要从剩下的 $n-1$ 个中选完整 $m$ 个。即 $C_{n-1}^m$。

所以，$C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$。这正是杨辉三角的递推公式。

---

三、杨辉三角的应用

3.1 二项式定理系数

杨辉三角的第 $n$ 行，正是二项式 $(a+b)^n$ 展开后的各项系数。

• $(a+b)^1 = 1a + 1b$ $\rightarrow$ 1, 1
• $(a+b)^2 = 1a^2 + 2ab + 1b^2$ $\rightarrow$ 1, 2, 1
• $(a+b)^3 = 1a^3 + 3a^2b + 3ab^2 + 1b^3$ $\rightarrow$ 1, 3, 3, 1

在解题时，如果让你求 $(x+1)^n$ 的展开式系数，可以直接打印杨辉三角。

3.1.1 扩展：关于“第 $n$ 行的所有数之和为 $2^n$”

这一条的原理主要有两种解释方式：代数推导和组合意义。

(1) 代数推导（利用二项式定理） 我们在文章前面提到过，杨辉三角的第 $n$ 行实际上就是 $(a+b)^n$ 展开后的系数。

\[(a+b)^n = C_n^0 a^n b^0 + C_n^1 a^{n-1} b^1 + \dots + C_n^n a^0 b^n\]

如果我们令 $a=1$ 且 $b=1$，代入上面的公式，就会神奇地发现：

\[(1+1)^n = C_n^0 \cdot 1^n \cdot 1^0 + C_n^1 \cdot 1^{n-1} \cdot 1^1 + \dots\]

即：

\[2^n = C_n^0 + C_n^1 + C_n^2 + \dots + C_n^n\]

而 $C_n^0, C_n^1, \dots$ 正是杨辉三角第 $n$ 行的所有数字。所以，它们的和一定等于 $2^n$。

(2) 组合意义（子集总数）

想象你有一个包含 $n$ 个不同元素的集合（比如 ${1, 2, \dots, n}$）。

$C_n^0$ 表示选 0 个元素的方案数（空集）； $C_n^1$ 表示选 1 个元素的方案数； … $C_n^n$ 表示选 $n$ 个元素的方案数（全集）。 把这一行所有数字加起来，意思就是“从中选出任意个元素的方案总数”，也就是这个集合的所有子集的数量。 对于集合中的每一个元素，它只有两种状态：“被选中” 或 “不被选中”。 $n$ 个元素，每个都有 2 种选择，根据乘法原理，总方案数就是 $\underbrace{2 \times 2 \times \dots \times 2}_{n个} = 2^n$。

3.2 动态规划求组合数

这是编程中最实用的功能。 直接利用阶乘公式 $C_n^m = \frac{n!}{m!(n-m)!}$ 计算组合数有两个大问题：

1. 溢出风险：$20!$ 就已经超过 long long 范围了，但 $C_{20}^{10}$ 其实并不大。
2. 计算量：频繁计算阶乘效率低，且涉及除法（取模时需要逆元）。

利用杨辉三角递推（其实就是动态规划），我们可以只用加法，安全、快速地计算出小范围内的所有组合数。

适用于 $N \le 2000$ 左右的情况。如果是 $N$ 很大但 $M$ 很小，或者 $N, M$ 都很大且需要取模，则需要用其他方法（如卢卡斯定理）。

---

四、代码实现 (C++)

下面展示如何利用二维数组生成杨辉三角，并查询组合数。

#include <iostream>
#include <vector>

using namespace std;

// 定义最大行数
const int MAXN = 20;

long long triangle[MAXN + 1][MAXN + 1];

void buildPascalTriangle() {
    // 初始化边界和递推
    for (int i = 0; i <= MAXN; i++) {
        triangle[i][0] = 1;       // 每行第一个是 1
        triangle[i][i] = 1;       // 每行最后一个是 1
        for (int j = 1; j < i; j++) {
            // 递推公式：头顶两数之和
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
}

void printTriangle() {
    for (int i = 0; i <= 10; i++) { // 打印前10行看看
        // 打印一些空格做格式化（仅仅为了美观，非必须）
        for(int k=0; k<10-i; k++) cout << "  ";
        
        for (int j = 0; j <= i; j++) {
            printf("%4lld", triangle[i][j]);
        }
        cout << endl;
    }
}

int main() {
    buildPascalTriangle();
    
    // 1. 打印图形
    cout << "=== 杨辉三角前10行 ===" << endl;
    printTriangle();
    
    // 2. 利用杨辉三角查询组合数
    // C(5, 2)
    int n = 5, m = 2;
    cout << "\n=== 组合数查询 ===" << endl;
    cout << "C(" << n << ", " << m << ") = " << triangle[n][m] << endl;
    
    // C(10, 4)
    n = 10; m = 4;
    cout << "C(" << n << ", " << m << ") = " << triangle[n][m] << endl;
    
    return 0;
}

代码运行结果演示

=== 杨辉三角前10行 ===
                      1
                    1   1
                  1   2   1
                1   3   3   1
              1   4   6   4   1
            1   5  10  10   5   1
          1   6  15  20  15   6   1
        1   7  21  35  35  21   7   1
      1   8  28  56  70  56  28   8   1
    1   9  36  84 126 126  84  36   9   1
    
=== 组合数查询 ===
C(5, 2) = 10
C(9, 4) = 126

---

五、实战演练：计算系数（洛谷 P1313）

题目描述： 给定一个多项式 $(ax + by)^k$，请求出多项式展开后 $x^n y^m$ 项的系数。结果对 $10007$ 取模。

核心考点： 二项式定理 + 组合数计算

解题思路： 根据二项式定理，$(ax+by)^k$ 的通项公式为：

\[T_{r+1} = C_k^r (ax)^{k-r} (by)^r = C_k^r a^{k-r} b^r x^{k-r} y^r\]

题目要求 $x^n y^m$ 项的系数，意味着对应的是 $x^n y^m$ 这一项。 即 $k-r = n$ 且 $r = m$（题目保证 $n+m=k$）。 所以，该项的系数为：

\[\text{系数} = C_k^m \times a^n \times b^m\]

为何使用杨辉三角？ 题目中 $k \le 1000$。虽然 10007 是质数，可以用卢卡斯定理或逆元，但直接用杨辉三角预处理 $C(k, m)$ 是最稳健、最不容易出错的方法（此范围 $O(k^2)$ 约为 $10^6$，非常快）。

代码核心片段：

// 1. 预处理杨辉三角 (只算到 k 行即可)
for (int i = 0; i <= k; i++) {
    c[i][0] = 1;
    c[i][i] = 1;
    for (int j = 1; j < i; j++)
        c[i][j] = (c[i-1][j-1] + c[i-1][j]) % 10007; // 边算边取模，完美
}

// 2. 计算答案
// ans = C(k, m) * a^n * b^m % 10007
long long ans = c[k][m]; 
ans = (ans * quick_pow(a, n)) % 10007; // 配合快速幂计算 a^n
ans = (ans * quick_pow(b, m)) % 10007; // 配合快速幂计算 b^m

cout << ans << endl;

代码核心片段分析（以连乘取模为例）

这段代码的核心逻辑是利用模运算的乘法性质来防止数据溢出。

我们以 3 个数连乘取模为例，公式如下： \((A \times B \times C) \pmod P = [((A \times B) \pmod P) \times C] \pmod P\)

即：步步取模。每乘一个数，就取一次模，最终结果不变。

1. 变量对应关系

在代码中，我们需要计算的是： \(\text{ans} = (C_k^m \times a^n \times b^m) \pmod{10007}\)

我们可以将其视为三个数 $A, B, C$ 的连乘：

• $A = C_k^m$ (即 c[k][m])
• $B = a^n$ (即 quick_pow(a, n))
• $C = b^m$ (即 quick_pow(b, m))
• $P = 10007$

2. 数学推导与代码执行对照

假设我们用小一点的数字来模拟： 计算 $(2 \times 3 \times 4) \pmod 5$。 直接计算：$2 \times 3 \times 4 = 24$， $24 \div 5 = 4 \dots 4$。结果为 4。

代码的分步执行过程（步步取模）：

1. 初始状态：

   long long ans = c[k][m]; // 对应 A
   

   假设 $A=2$，则 ans = 2。

2. 第一步乘法：

   ans = (ans * quick_pow(a, n)) % 10007; // 对应 (A * B) % P
   

   假设 $B=3, P=5$。

   • 计算乘积：$ans \times B = 2 \times 3 = 6$
   • 取模：$6 \pmod 5 = 1$
   • 此时 ans = 1。
3. 第二步乘法：

   ans = (ans * quick_pow(b, m)) % 10007; // 对应 (ans * C) % P
   

   这里用的是上一步计算出的 ans（即 1）。假设 $C=4$。

   • 计算乘积：$ans \times C = 1 \times 4 = 4$
   • 取模：$4 \pmod 5 = 4$
   • 此时 ans = 4。

结论：最终结果 4 与直接计算的结果一致。

3. 为什么要这样做？

虽然本题模数 $10007$ 很小，直接算也不会溢出 long long，但在算法竞赛中，通常模数 $P$ 很大（如 $10^9+7$）。 如果不“步步取模”，直接算 $A \times B \times C$，结果可能会是一个巨大的天文数字，远超计算机整数类型的存储上限（即溢出）。通过步步取模，我们保证了中间结果永远不会超过 $P \times P$（约 $10^{18}$ 范围内），从而可以安全地使用 long long 存储。

---

六、总结

杨辉三角形是连接几何（三角形结构）与代数（组合数、二项式定理）的桥梁。在 GESP 八级考试中，主要考察以下几点：

1. 基本性质：要知道第 $n$ 行第 $m$ 列对应 $C_n^m$。
2. 递推构造：能够手写代码构建杨辉三角数组（DP思想）。
3. 行和性质：第 $n$ 行的所有数之和为 $2^n$（对应集合所有子集的总数）。
4. 组合数计算：利用杨辉三角解决不需要取模或模数不是质数的组合数计算问题。

注：关于“不需要取模或模数不是质数时的组合数计算”

这一条是针对编程竞赛（算法竞赛）中常见的坑点。

为什么要用杨辉三角（递推法）？ 通常计算组合数 $C_n^m$ 有两种方法：

公式法：$C_n^m = \frac{n!}{m!(n-m)!}$ 递推法（杨辉三角）：$C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$ 公式法的问题在于那个除法。

在计算机中，整数运算 $a / b \pmod p$ 不等于 $(a \pmod p) / (b \pmod p)$。 要计算模运算下的除法，必须转换成 乘以 $b$ 的逆元，即 $a \cdot b^{-1} \pmod p$。 关键限制：只有当模数 $p$ 是质数（且 $b$ 不是 $p$ 的倍数）时，我们可以简单地用费马小定理求逆元。 如果题目要求的模数 $p$ 不是质数（比如 $p=1000$），或者根本不取模（但在 long long 范围内），公式法就非常麻烦：

不取模时：中间的阶乘 $n!$ 极易溢出（21! 就爆了 unsigned long long），通过公式算出结果很难。 模数组合数非质数时：无法使用费马小定理求逆元，需要用扩展欧几里得算法求逆元，或者分解质因数，代码极其复杂且容易写错。 杨辉三角的优势： 它全程只使用加法（$dp[i][j] = dp[i-1][j-1] + dp[i-1][j]$）。

没有除法：不需要担心除不尽，也不需要求逆元。 适用性广：无论模数 $p$ 是质数还是合数，加法取模恒成立 $(a+b) \pmod p = (a%p + b%p) % p$。 防溢出：可以直接在计算过程中取模，或者直接利用 long long 存储最终结果（只要最终结果不超）。 总结：只要 $n$ 的范围较小（比如 $n \le 2000$），无论模数是什么妖魔鬼怪，这套杨辉三角递推代码都是通杀的“万金油”解法。

掌握了杨辉三角，我们就有了处理简单组合计数问题的有力武器。

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号