Appearance
第2章 计数原理
🎯 本章学习目标
通过本章的学习，你将能够：
- 掌握加法原理：理解分类计数思想，能判断何时用加法
- 掌握乘法原理：理解分步计数思想，能判断何时用乘法
- 辨析两大原理：能准确区分"分类"还是"分步"，选择正确的运算
- 组合使用原理：能解决同时需要分类和分步的复杂计数问题
- 避免常见错误：知道分类不重不漏、分步相互独立等注意事项
- 解决典型问题：能解决路线、染色、数位、网格路径等经典计数问题
- 理解容斥思想：知道分类重叠时需要用容斥原理修正
- 建立计数直觉：培养"不重不漏"的计数思维
- 理解编程意义：知道计数原理是DP、组合数学的基础
- 应对真题题型：能解决选择、判断、计算等各类计数原理题目
🗺️ 本章知识图谱
计数原理
├── 加法原理（分类计数）
│ ├── 核心：完成一件事有n类办法
│ ├── 公式：总数 = m1 + m2 + ... + mn
│ ├── 关键词：要么...要么...
│ ├── 要求：类与类之间互斥（不重不漏）
│ └── 典型场景
│ ├── 多种交通方式选一种
│ ├── 多类套餐选一种
│ └── 分类讨论问题
├── 乘法原理（分步计数）
│ ├── 核心：完成一件事分n个步骤
│ ├── 公式：总数 = m1 × m2 × ... × mn
│ ├── 关键词：先...再...
│ ├── 要求：步与步之间独立
│ └── 典型场景
│ ├── 路线中转（甲→乙→丙）
│ ├── 多步选择（衣裤搭配）
│ └── 排列问题（逐步选位置）
├── 辨析方法
│ ├── 看关系：互斥用加，独立用乘
│ ├── 看描述：要么...要么...=加；先...再...=乘
│ └── 验证：用小例子手动枚举
├── 组合使用
│ ├── 先分类，每类内部分步
│ └── 先分步，每步内部分类
├── 易错点
│ ├── 分类有重叠 → 容斥原理
│ ├── 分步不独立 → 重新分步
│ ├── 首位不能为0 → 单独处理
│ └── 染色问题 → 先染枢纽区域
└── 典型应用
├── 路线计数
├── 染色问题
├── 数位计数
├── 网格路径
└── 排队问题一、🧭 为什么八级还要学"数数"？
很多同学觉得"加法、乘法"是小学知识，八级考这个是不是太简单？恰恰相反。 GESP 八级的计数题，难的不再是计算，而是建模：
- 一道网格路径题，到底是
3+2=5还是3×2=6？判错符号，答案全错； - 一道染色题，分步顺序选错，就会重复计数或遗漏方案；
- 一道数位编程题，分类标准不互斥，代码写得再漂亮也是错的。
🔥 高频考点：加法原理与乘法原理的辨析，几乎是八级选择题/判断题的"必点菜"；而编程题中的路径计数、数位统计、方案数 DP，其状态转移方程本质上就是两大原理的反复套用。
二、加法原理：分类计数 ➕
定义：完成一件事有 n 类办法，第 1 类有 种方法，第 2 类有 种方法……第 n 类有 种方法，且各类办法相互独立、互斥（任选一类中的一种即可完成这件事），那么完成这件事共有：
生活实例：食堂午餐有 3 种中餐套餐、4 种面食、2 种西餐，只选一份，共有 种选择。
关键词："或"——选中餐或面食或西餐，选哪一类都能独立完成任务。
⚠️ 易错点：分类必须"不重不漏" 各类办法之间不能有重叠（同一方案被算进两类 → 重复计数），也不能有遗漏（某类方案没被统计 → 结果偏小）。这就是数学上常说的分类要满足 MECE（相互独立、完全穷尽）。
三、乘法原理：分步计数 ✖️
定义：完成一件事需要 n 个步骤，做第 1 步有 种方法，做第 2 步有 种方法……做第 n 步有 种方法，各步骤相继完成、缺一不可，那么完成这件事共有：
生活实例：一份套餐含 1 荤（3 种选择）、1 素（4 种选择）、1 汤（2 种选择），各选一样配成一餐，共有 种搭配。
关键词："且"——选荤且选素且选汤，每一步都走完才算完成。
🔥 高频考点：乘法原理中，后一步的方法数可能依赖前一步的选择（如染色问题中"相邻区域不同色"，第二步比第一步少 1 种选择），但只要"每一步的选择数"能确定，就照常相乘。
四、判断标准：分类用加，分步用乘 🤔
拿到一道计数题，先问自己三个问题：
| 判断问题 | 回答"是" | 回答"否" |
|---|---|---|
| 这件事是"选一种就完事"吗？ | 分类 → 加法 | 继续往下问 |
| 这件事需要"一步步全做完"吗？ | 分步 → 乘法 | 需要拆分重组 |
| 各类/各步之间会互相影响吗？ | 受影响的步骤单独算选择数 | 直接套用 |
一句话口诀：
📌 分类用加（"或"的关系），分步用乘（"且"的关系）；分类要不重不漏，分步要顺序合理。
对比辨析：
| 对比维度 | 加法原理 | 乘法原理 |
|---|---|---|
| 逻辑关系 | 分类（或） | 分步（且） |
| 完成条件 | 任取一类中的一种即完成 | 所有步骤全部完成才完成 |
| 各类/步关系 | 相互独立、互斥 | 相继进行，缺一不可 |
| 典型错误 | 分类重叠 / 遗漏 | 分步顺序不当导致重复计数 |
五、两大原理的组合使用 🧩
复杂题目往往需要两大原理嵌套使用，有两种典型结构：
① 先分类，后分步：先把方案分成几大类（加法），每一大类内部再分步计算（乘法）。
例：选餐问题中"吃套餐"分中餐、面食两类（加），每类都要选主食+饮料（乘）。
② 先分步，后分类：先把事情拆成几个步骤（乘法骨架），某一步内部存在多种情况需要分类讨论（加法填充）。
例：染色问题分步给区域染色（乘），染某个区域时要按"与前一区域同色/不同色"分类讨论（加）。
💡 经验：真题中"先分类后分步"更常见。拿到题先按最显眼的差异分类（如位数、奇偶、是否经过某点），再在每类内分步。
六、典型例题（难度递进）
例1（单选风格）｜选餐问题
题目：某餐厅菜单上有中餐套餐 5 种、面食 3 种、小吃 4 种。小明打算：① 只点一种主食，有多少种点法？② 点一种主食 + 一种小吃，有多少种点法？
解析： 注意"主食"和"小吃"是两个独立类别——主食 = 中餐套餐 + 面食，共 种；小吃 4 种单独算。
- ① 从主食类中任选一种，分类计数： 种（加法原理）。
- ② 选主食和选小吃是两个都要完成的步骤： 种（乘法原理）。
⚠️ 易错点：别把小吃也归为主食。如果误写成 再乘 ，就会犯两类错误：① 多算 4 种；② 把小吃的 4 种重复乘了一次。正确的分步交叉验证：中餐配小吃 + 面食配小吃 = 32，结果一致。
代码验证（枚举所有点法）：
cpp
#include <iostream>
using namespace std;
int main() {
// 主食 = 中餐套餐 + 面食，小吃独立
int staple_cn = 5; // 中餐套餐
int staple_face = 3; // 面食
int snack = 4; // 小吃
int staple = staple_cn + staple_face; // 主食 = 8
int combo = staple * snack; // 主食+小吃 = 32
cout << "只点主食: " << staple << endl; // 8
cout << "主食+小吃: " << combo << endl; // 32
return 0;
}例2（单选风格）｜网格路径计数
题目：如图，从街道的 A 点走到 B 点，只能向右或向下走，共需向右走 3 段、向下走 3 段。问共有多少条不同路线？
解析：对每个路口，到达它的路线只有两个来源：从正上方下来、从正左边过来。两类路线互斥，用加法原理递推：
边界：第一行、第一列的路口都只有 1 条路线。逐格算出终点值为 20。
🔥 高频考点：这个递推就是著名的"网格路径数"，答案本质是组合数 ——为什么？因为 6 步里选 3 步向右（其余向下），这正是第3期排列组合要讲的内容，先混个脸熟！
代码验证：
cpp
#include <iostream>
using namespace std;
int main() {
int n = 3, m = 3; // 向右 n 段，向下 m 段
long long dp[20][20] = {0};
dp[0][0] = 1;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++) {
if (i == 0 && j == 0) continue;
if (i > 0) dp[i][j] += dp[i-1][j]; // 从上方来（一类）
if (j > 0) dp[i][j] += dp[i][j-1]; // 从左方来（另一类）
}
cout << dp[n][m] << endl; // 20
return 0;
}💡 注意：
dp[i][j] = 上方 + 左方这一步，就是把加法原理写进了代码——DP 计数题的转移方程，几乎都能找到计数原理的影子。
例3（单选风格）｜数位问题：1~999 中不含数字 5 的数
题目：在 1 到 999 的整数中，十进制表示里不含数字 5 的数共有多少个？
解析：这是典型的先分类、后分步：
- 第一类：一位数。1~9 中去掉 5，共 8 个；
- 第二类：两位数。十位可取 1~9 除 5（8 种），个位可取 0~9 除 5（9 种），分步相乘： 个；
- 第三类：三位数。百位 8 种，十位 9 种，个位 9 种： 个。
三类相加： 个。
⚠️ 易错点：两位数/三位数的首位不能为 0，所以首位是"8 种"而不是"9 种"；其余位才是 9 种。数位问题中"首位特判"是第一大坑。
代码验证（暴力枚举，小数据范围可直接检验）：
cpp
#include <iostream>
using namespace std;
int main() {
int cnt = 0;
for (int x = 1; x <= 999; x++) {
int t = x, ok = 1;
while (t) {
if (t % 10 == 5) { ok = 0; break; }
t /= 10;
}
cnt += ok;
}
cout << cnt << endl; // 728
return 0;
}例4（单选风格）｜染色问题入门
题目：地图上有 A、B、C 三个区域，其中 A 与 B 相邻、B 与 C 相邻，A 与 C 不相邻。用 4 种颜色给三个区域染色，要求相邻区域颜色不同，共多少种方案？
**解析：**分步染色，优先染"相邻关系最多"的区域 B：
- 第 1 步染 B：4 种选择；
- 第 2 步染 A：与 B 不同色，3 种；
- 第 3 步染 C：只需与 B 不同色（A、C 不相邻，可以同色），3 种。
乘法原理： 种。
变式：若 A 与 C 也相邻（三个区域两两相邻），则 C 还要与 A 不同色： 种。
⚠️ 易错点： ① 染色顺序很关键！若先染 A 再染 B 再染 C，本题也是 ，但遇到环形、复杂相邻图时，顺序选错会让后染的区域约束说不清，被迫分类讨论甚至重复计数。口诀：先染邻居多的"枢纽"区域。 ② "不相邻"意味着"可同色可不同色"，约束只有"相邻不同色"一条，别擅自加戏。
代码验证（枚举所有染色方案）：
cpp
#include <iostream>
using namespace std;
int main() {
int cnt = 0;
for (int a = 0; a < 4; a++)
for (int b = 0; b < 4; b++)
for (int c = 0; c < 4; c++)
if (a != b && b != c) // 仅 A-B、B-C 相邻
cnt++;
cout << cnt << endl; // 36
return 0;
}例5（编程风格计数题）｜统计不含数字 4 的数
题目：给定正整数 （），统计 中十进制表示不含数字 4 的整数个数。
思路（先分类后分步）：
- 第一类：位数比 n 少的数。k 位数中，首位可取 1~9 除 4（8 种），其余每位可取 0~9 除 4（9 种），故 k 位数有 个——类内分步用乘法，各位数之间用加法求和。
- 第二类：与 n 位数相同的数。从高位到低位逐位扫描：当前位取"比 n 该位小且不等于 4"的每种数字时（分类，加法累计），后面剩余位可任意取（每位 9 种，乘法）；若 n 自身某位就是 4，则含 4 的前缀之后不必再统计，直接停止；扫描结束若 n 本身不含 4，再补上 n 自己。
🔑 点击查看答案与解析
参考代码（C++11）：
cpp
#include <iostream>
#include <string>
using namespace std;
int main() {
long long n;
cin >> n;
string s = to_string(n);
int len = s.size();
long long p9[15];
p9[0] = 1;
for (int i = 1; i < 15; i++) p9[i] = p9[i-1] * 9;
long long ans = 0;
// 第一类：位数少于 len 的数（按位数分类，加法原理）
long long ways = 8; // 1 位数：首位 8 种
for (int k = 1; k < len; k++) {
ans += ways; // k 位数的合法个数
ways *= 9; // 位数每多一位，后位 9 种（乘法）
}
// 第二类：与 n 同位数，逐位分类讨论
bool valid = true;
for (int i = 0; i < len; i++) {
int d = s[i] - '0';
int lo = (i == 0 ? 1 : 0); // 首位不能为 0
int choices = 0;
for (int x = lo; x < d; x++) // 当前位可取的更小数字
if (x != 4) choices++; // 分类：每种选择互斥
int remain = len - i - 1;
ans += choices * p9[remain]; // 后 remain 位任意：9^remain（乘法）
if (d == 4) { valid = false; break; } // n 前缀含 4，后续无需统计
}
if (valid) ans += 1; // n 本身不含 4
cout << ans << endl;
return 0;
}自测样例：输入 10 → 输出 9（1,2,3,5,6,7,8,9,10）；输入 4 → 输出 3（1,2,3）；输入 999 → 输出 728（与例3互相印证 ✓）。
🔥 高频考点：这类"数位计数"题是八级编程题的常客。暴力枚举在 时会超时，而用计数原理按位拆分后是 ——这就是"用数学代替枚举"的威力，也是第9期算法优化的伏笔。
七、易错点清单 📋
| 易错点 | 错误表现 | 正确做法 |
|---|---|---|
| 分类重叠 | 同一方案被算进多个类别，结果偏大 | 分类标准互斥（MECE），算完反问"有没有方案被数了两次" |
| 分类遗漏 | 某类方案没考虑到，结果偏小 | 分类后检验边界情况（首位为0、空方案、n自身） |
| 分步顺序错误 | 后一步的选择数说不清，或隐性重复 | 优先安排约束最多的步骤（如染色先染枢纽区域） |
| 分步误用加法 | "甲到乙3条路、乙到丙2条路"写成 3+2 | 路线需两段都走，分步用乘：3×2=6 |
| 分类误用乘法 | "三类套餐只选一种"写成 5×3×4 | 任选一类即完成，分类用加 |
| 首位特判遗漏 | 数位题中首位按 9 种/10 种算 | 首位不能为 0，单独确定选择数 |
八、与下一章的衔接：从"原理"到"公式" 🔗
本章两大原理回答的是"怎么数"，但当对象变多时——
- 从 5 个人中选 3 个排成一排，有多少种排法？（乘法原理连乘：）
- 从 5 个人中选 3 个组成小组（不排序），有多少种选法？（需要"分组"新工具）
- 例2 的网格路径数为什么恰好等于 ？
这些问题的系统化答案，就是排列数 与组合数 。它们不是新东西，而是加法/乘法原理在"有序选取"与"无序选取"两种场景下的浓缩公式；再往后，第4章的杨辉三角本质就是组合数的递推表 ——看，又是加法原理！
💡 计数原理是整条数学链的"地基"：本章学牢，第3章排列组合、第4章杨辉三角都会事半功倍。
九、📝 实战练习
练习题 1（单选题）
题目： 小明有 3 本不同的数学书、4 本不同的语文书、5 本不同的英语书。他要选一本书带出门，共有多少种选法？（ ）
A. 12
B. 60
C. 3+4+5=12
D. 3×4×5=60
🔑 点击查看答案与解析
答案： A
解析： "选一本书带出门"——要么选数学书，要么选语文书，要么选英语书。这是分类，用加法原理。
总选法 = 3 + 4 + 5 = 12
选 A。
💡 关键词"选一本"= 只选一个类别里的一本 → 分类用加法。
练习题 2（单选题）
题目： 小明有 3 件不同的上衣、4 条不同的裤子、2 双不同的鞋子。一套穿搭包括一件上衣、一条裤子和一双鞋子，共有多少种不同的穿搭方式？（ ）
A. 9
B. 24
C. 3+4+2=9
D. 3×4×2=24
🔑 点击查看答案与解析
答案： B
解析： 搭配一套衣服，需要"先选上衣，再选裤子，再选鞋子"——这是分步，用乘法原理。
总穿搭数 = 3 × 4 × 2 = 24
选 B。
🍎 生活比喻：每选一件上衣，都可以搭配 4 条裤子；每一种衣裤搭配，又可以配 2 双鞋。所以是乘的关系。
练习题 3（判断题）
题目： "从 5 个人中选 1 个人当班长，再选 1 个人当副班长（不能同一人）"，这道题用加法原理，选法有 5 + 4 = 9 种。（ ）
🔑 点击查看答案与解析
答案： 错误 ❌
解析： "先选班长，再选副班长"——有先后顺序，是分步，用乘法原理。
选法 = 5 × 4 = 20 种，不是 9 种。
什么时候用加法？比如"选一个人当学生代表，可以从5个男生或4个女生中选"——这是分类，用加法（5+4=9）。
🔥 高频考点：判断用加还是用乘，就看是"选一个"还是"都要选"。选一个 = 加法；都要选 = 乘法。
练习题 4（单选题）
题目： 从 A 到 B 有 3 条路，从 B 到 C 有 2 条路，从 A 到 C 有 4 条直达路线。从 A 到 C 共有多少种不同的走法？（ ）
A. 9
B. 10
C. 24
D. 5
🔑 点击查看答案与解析
答案： B
解析： 从 A 到 C 有两类走法：
- 经 B 中转：A→B→C，分步用乘法 → 3 × 2 = 6 种
- 直达：4 种
两类走法互斥（要么直达，要么中转），所以用加法：
总走法 = 6 + 4 = 10 种
选 B。
💡 解题步骤：先分类（直达 vs 中转），每类内部再看是分步还是分类。
练习题 5（单选题）
题目： 用数字 1, 2, 3, 4, 5 可以组成多少个不同的两位数（数字可以重复使用）？（ ）
A. 10
B. 20
C. 25
D. 15
🔑 点击查看答案与解析
答案： C
解析： 组成两位数，分两步：
- 选十位：有 5 种选择（1~5）
- 选个位：有 5 种选择（可以重复，所以还是 5 种）
分步用乘法：5 × 5 = 25
选 C。
⚠️ 如果题目说"数字不能重复"，就是 5 × 4 = 20。注意看清楚题目要求！
练习题 6（单选题）
题目： 用 3 种颜色给下图中 3 个区域染色，要求相邻区域颜色不同。共有多少种染色方案？（区域 A 与 B 相邻，B 与 C 相邻，A 与 C 不相邻）（ ）
A. 6
B. 8
C. 12
D. 27
🔑 点击查看答案与解析
答案： C
解析： 按顺序染色，先染中间的 B（枢纽区域）：
- 染 B：3 种选择
- 染 A：不能和 B 同色 → 2 种选择
- 染 C：不能和 B 同色，但可以和 A 同色 → 2 种选择
分步用乘法：3 × 2 × 2 = 12
选 C。
💡 技巧：染色问题通常先染约束最多的区域（和最多邻居相邻的），也就是"枢纽区域"。
练习题 7（单选题）
题目： 在一个 3×2 的网格中，从左上角走到右下角，每次只能向右或向下走一步，共有多少种走法？（ ）
A. 5
B. 6
C. 10
D. 12
🔑 点击查看答案与解析
答案： C
解析： 3×2 的网格，从左上到右下：
- 需要向下走 3 步
- 需要向右走 2 步
- 一共走 5 步
问题转化为：在 5 步中选 3 步向下（剩下 2 步向右），有多少种选法？
这是组合数 C(5,3) = C(5,2) = 5×4 / 2×1 = 10
也可以用 DP 验证：
1 1 1
1 2 3
1 3 6
1 4 10最后一个格子是 10 ✓
选 C。
💡 m×n 网格从左上到右下（只能右/下）的路径数 = C(m+n, m) = C(m+n, n)
练习题 8（判断题）
题目： 一个班有 30 人，其中 15 人喜欢数学，20 人喜欢语文。那么喜欢数学或语文的总人数一定是 15 + 20 = 35 人。（ ）
🔑 点击查看答案与解析
答案： 错误 ❌
解析： 加法原理的前提是"类与类互斥（不重叠）"。但这里"喜欢数学"和"喜欢语文"可能有重叠（有人两科都喜欢），所以不能直接相加。
正确做法（容斥原理）： 喜欢数学或语文的人数 = 喜欢数学的 + 喜欢语文的 - 两科都喜欢的
因为有重叠，所以总数一定小于等于 35，而且不可能超过全班 30 人。
🔥 高频考点：分类时一定要注意"不重不漏"。如果有重叠，要用容斥原理减回去。
十、📊 考点总结表
| 考点 | 重要程度 | 出题形式 | 易错点 |
|---|---|---|---|
| 加法原理（分类） | ⭐⭐⭐⭐⭐ | 选择/判断 | 分类必须互斥不重叠 |
| 乘法原理（分步） | ⭐⭐⭐⭐⭐ | 选择/判断 | 分步必须相互独立 |
| 两大原理辨析 | ⭐⭐⭐⭐⭐ | 选择/判断 | 选一个=加，都要选=乘 |
| 组合使用（先分类再分步） | ⭐⭐⭐⭐ | 选择/计算 | 分清哪层是分类哪层是分步 |
| 路线计数 | ⭐⭐⭐⭐ | 选择/计算 | 直达和中转是两类 |
| 染色问题 | ⭐⭐⭐⭐ | 选择/编程 | 先染枢纽区域；相邻不同色 |
| 数位计数 | ⭐⭐⭐⭐ | 选择/编程 | 首位不能为0 |
| 网格路径计数 | ⭐⭐⭐⭐⭐ | 选择/DP | C(m+n,m) 或 DP递推 |
| 容斥思想 | ⭐⭐⭐⭐ | 选择/判断 | 重叠部分要减回去 |
| 不重不漏原则 | ⭐⭐⭐⭐⭐ | 判断/选择 | 计数的基本要求 |
⭐ 必背速记卡
┌─────────────────────────────────────────────┐
│ 计数原理 · 必背速记卡 │
├─────────────────────────────────────────────┤
│ 1. 加法原理：分类计数，类与类互斥 │
│ 2. 乘法原理：分步计数，步与步独立 │
│ 3. 选一个 = 加法；都要选 = 乘法 │
│ 4. 要么...要么... = 分类 = 加法 │
│ 5. 先...再... = 分步 = 乘法 │
│ 6. 组合使用：先分类，每类内部分步 │
│ 7. 计数原则：不重不漏 │
│ 8. 分类有重叠 → 容斥原理减回去 │
│ 9. 路线中转：分步相乘；直达+中转：分类相加 │
│ 10. 染色问题：先染枢纽区域（邻居最多的） │
│ 11. 数位计数：首位不能为0，单独处理 │
│ 12. 数字可重复：每步都有n种 │
│ 13. 数字不重复：每步少一种 │
│ 14. 网格路径（右+下）：C(m+n, m) │
│ 15. 计数原理是排列组合和DP的基础 │
└─────────────────────────────────────────────┘