E3 数学与计数

对应大纲： 2.1.5-2（初等数学）、2.1.5-3（初等数论）、2.1.5-4（离散与组合数学）+ 逻辑运算

分量： 每年稳定 2~4 道单选。排列组合几乎每年都出。

一、排列与组合

$$A(n,m) = \frac{n!}{(n-m)!} \quad\text{（有顺序）} \qquad C(n,m) = \frac{n!}{m!(n-m)!} \quad\text{（无顺序）}$$

常用值背下来：

对称性：$C(n,m) = C(n, n-m)$ —— 算 $C(22,19)$ 时改算 $C(22,3)$。

⚠️ 四个必须分清的套路

① 「至少一个 X」→ 用补集

$$\text{答案} = \text{总数} - \text{一个 X 都没有}$$

CSP 2023 第 14 题：10 男 12 女选 3 人至少 1 女 $= C(22,3) - C(10,3) = 1540 - 120 = 1420$

⚠️ 算完一定要真的减那一下——选项里必定有一个是「忘了减」的总数。

② 「每组至少一个」→ 枚举分配方案，不能用补集

CSP 2024 第 3 题：A(4人) B(3人) C(3人) 选 4 人，每部门至少 1 人。补集会重叠，只能枚举：

📝 一句话区分：只有一个「组」时用补集；有多个「组」且每组都有下限时枚举分配。

③ 「必须相邻」→ 捆绑法；「不能相邻」→ 插空法

捆绑：把必须相邻的 $k$ 个捆成 1 个整体，排完再乘 $k!$（内部顺序）。

• CSP 2024 第 14 题：5 男 3 女、3 女相邻 $= 6! \times 3! = 720 \times 6 = 4320$
• CSP 2020 第 10 题：5 人、双胞胎相邻 $= 4! \times 2! = 48$

插空：先排其他人，再往产生的空隙里插。

④ 相同物品分给不同的人 → 隔板法

$$n \text{ 个相同物品分给 } k \text{ 个不同的人，每人至少一个} = C(n-1,\ k-1)$$

CSP 2020 第 14 题：10 个名额分 7 个班，每班至少 1 个 $= C(9,6) = 84$

⚠️ 三个条件缺一不可：物品相同、人不同、每人至少一个。

⚠️ 如果「东西相同、袋子也相同」就完全不是隔板法了，那是整数分拆（CSP 2019 第 7 题：8 个相同的球放 5 个相同的袋子 = 18 种），没有公式，只能有序枚举（从最大的一份递减）。

二、鸽巢原理（抽屉原理）

$$n \text{ 个物品放进 } k \text{ 个抽屉，必有一个抽屉至少 } \left\lceil \frac{n}{k} \right\rceil \text{ 个}$$

CSP 2019 第 12 题：13 张牌分 4 种花色 → 至少 $\lceil 13/4 \rceil = 4$ 张同花色。

📝 判断方法：想最坏情况（尽量平均分）。 $13 = 3+3+3+4$，仍有一堆是 4 张；而 $3+3+3+3$ 只有 12 张，装不下。

⚠️ 「至少」问的是「无论怎么分都能保证达到」的数，不是「最多可能有多少」。

三、初等数论

100 以内的 25 个质数（必背）

 2  3  5  7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97

⚠️ $91 = 7 \times 13$ 不是质数！ 它是初赛最经典的陷阱（CSP 2019 第 9 题的干扰项）。判素数要试除到 $\sqrt n$，$91$ 要试到 $9$ 才能发现 $7$。

辗转相除法（欧几里得算法）

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

$$\gcd(377, 319) \to \gcd(319, 58) \to \gcd(58, 29) \to \gcd(29, 0) = 29$$

⚠️ CSP 2025 第 16 题整道大题就是围绕这五行代码出的，把递归写成 gcd(a, a % b) 会导致函数恒返回 a（但不会死循环，实测已确认）。

约数个数与约数之和（考过）

若 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$：

$$d(n) = \prod (a_i + 1), \qquad \sigma(n) = \prod \frac{p_i^{a_i+1}-1}{p_i - 1}$$

例：$1000 = 2^3 \times 5^3$ → $d = 4 \times 4 = 16$，$\sigma = 15 \times 156 = 2340$（CSP 2021 第 18 题的答案）

📝 $d(100000) = d(2^5 5^5) = 6 \times 6 = 36$ —— CSP 2019 第 16 题用到。

进位次数公式（勒让德公式）

$$\text{从 }0\text{ 数到 }n\text{ 的 }k\text{ 进制总进位次数} = \left\lfloor \frac{n}{k} \right\rfloor + \left\lfloor \frac{n}{k^2} \right\rfloor + \cdots$$

⚠️ CSP 2020 第 17 题（$n$ 大到 $10^{15}$，不可能模拟）就靠这个公式。它和「$n!$ 里质因子 $p$ 的个数」是同一个式子。

四、逻辑运算与真值表

德摩根定律（常考）：

$$\neg(a \wedge b) = \neg a \vee \neg b \qquad \neg(a \vee b) = \neg a \wedge \neg b$$

⚠️ 逻辑表达式题一律画真值表，别心算。 三个变量只有 8 行，画完必对；「一眼看出来」才是失分主因。

📝 秒杀技巧：如果某个变量已知为假，那么所有以 && 它 收尾的表达式立刻为假。CSP 2020 第 3 题的 A、B、C 三个选项都以 $\wedge z$ 结尾而 $z$ 为假——一眼灭三个。

⚠️ 短路求值：a && b 中若 a 为假，b 根本不会被计算；a || b 中若 a 为真，b 也不会算。这在阅读程序题里会考（比如 i < n && a[i] == x 靠短路避免越界）。

五、其他常考

杨辉三角

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

第 $n$ 行第 $m$ 个数（从 0 编号）就是 $C(n,m)$；每行之和为 $2^n$。

集合

• 元素的互异性、无序性、确定性
• $|A \cup B| = |A| + |B| - |A \cap B|$（容斥原理）
• 三个集合：$|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$

斐波那契与递推

$f(n) = f(n-1) + f(n-2)$，$1,1,2,3,5,8,13,21,34,55,\dots$

⚠️ 「取模的递推求很大的下标」一定是找周期。 CSP 2025 第 8 题：$f[n] = (f[n-1]+f[n-2]) \bmod 7$，周期是 16，$2025 \bmod 16 = 9$，查表即得。做法固定：一直往下算，直到出现连续两项和开头相同。

递归题的通用做法

📝 一律列表格从小往大填，别在脑子里展开调用树。

CSP 2021 第 13 题、CSP 2025 第 3 题都是这个套路——solve(1)、solve(2)、solve(3)……填到题目问的那个为止，三分钟，零风险。

30 秒自测

1. $C(9,4)$ 等于多少？$C(22,19)$ 怎么快速算？
2. 「至少一个女生」和「每个班至少一个名额」，各用什么方法？
3. 3 个女生必须相邻，5 个男生随意，一共几种排法？
4. 13 张牌 4 种花色，至少几张同花色？
5. $91$ 是质数吗？
6. $\gcd(377, 319)$ 是多少？
7. $1000$ 有几个约数？约数之和是多少？
8. 已知 $z$ 为假，(x && y) && z 的值是什么？不用管 $x, y$ 吗？