公式表

一个正整数的阶乘，是所有小于或等于它的正整数的乘积。也就是说，

把 $n$ 个物体排成一排，方法数是 $n!$。

把 $n$ 个物体排成一圈，如果同一种排法旋转后不算不同，方法数是 $(n-1)!$。

把 $n$ 个物体排成一圈，如果同一种排法的旋转和镜像都不算不同，方法数是

从总共 $n$ 个物体中取出 $k$ 个排好，方法数是

一个单词的字母重排方法数是

其中 $n$ 是字母个数，$d_1, d_2, d_3, \ldots$ 是单词中每个出现不止一次的字母各自出现的次数。

从总共 $n$ 个物体中选出 $k$ 个，方法数是

通常读作“$n$ 选 $k$”。

一个有 $n$ 个元素的集合，子集个数是 $2^n$。

当所有结果都等可能时，

很多计数问题和概率问题，都可以拆成几种情况来解：分别数出每种情况，再加起来。

做分类讨论时，总要设法让需要处理的情况尽量少。

如果题目问的是：已知事件 $B$ 已经发生，事件 $A$ 发生的概率是多少，那么只有 $B$ 中的结果仍然可能出现：

当各个结果不是等可能时，就改用概率来算：

容斥原理（PIE）是一种计数方法：它求出至少满足若干性质之一的元素个数，同时保证满足不止一个性质的元素不会被数两次。

$|A \cup B|$ 表示 $A$ 与 $B$ 的并集的元素个数：所有属于 $A$ 或属于 $B$（或同时属于两者）的元素。重复的元素只写一次。

$|A \cap B|$ 表示 $A$ 与 $B$ 的交集的元素个数：只包括同时属于两个集合的元素。

对两个集合 $A_1$ 和 $A_2$，

简单地说，先数出 2 类“东西”各有多少种可能，再减去重复的部分。

对三个集合 $A_1$、$A_2$、$A_3$，

先数出 3 类“东西”各有多少种可能，再减去 3 对集合中各自重复的部分，最后把同时属于 3 个集合的元素加回来。

若 $A_1, A_2, \ldots, A_n$ 是有限集合，则

加上单个集合，减去每两个的交集，加上每三个的交集，正负号一直交替下去。

把 $n$ 个相同的物品放进 $k$ 个可区分的盒子里，方法数是

隔板法极其有用，而且常常可以根据情况灵活变通。例如，如果每个盒子里至少要有 1 个物品，就先给每个盒子放 1 个，再对 $n - k$ 个物品和 $k$ 个可区分的盒子使用公式：

对称性：

各项之和：

当 $n \ge 1$ 时，

也就是说，$\binom{n}{0} + \binom{n}{2} + \cdots = \binom{n}{1} + \binom{n}{3} + \cdots$

范德蒙恒等式：

平方和：

杨辉三角（帕斯卡三角）是由二项式系数排成的三角形数表。它包含许多规律，能让复杂的计算简单得多。

第 $n$ 行（把最上面一行算作第 0 行）依次是 $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$。下面把前几行写成二项式系数；“演示给我看”会用数字显示第 0 行到第 10 行。

帕斯卡恒等式：

曲棍球棒恒等式：

推广形式：

在 $m \times n$ 的长方形方格中，各种大小的长方形一共有

个。

$n \times n$ 的正方形方格中，正方形的个数是

只向上和向右走，从 $(0,0)$ 走到点 $(m,n)$ 的方法数是

在一个多面体中，把每个面的边数加起来，得到的是多面体棱数的 2 倍。这是因为每条棱都是 2 个面的边。

把每个顶点连着的棱数加起来，得到的也是棱数的 2 倍，因为每条棱在 2 个不同的顶点处各被数了一次。

例如，正方体每个面有 4 条边，共 6 个面，所以它有 $\frac{4 \times 6}{2} = 12$ 条棱。另外，每个顶点连着 3 条棱，共 8 个顶点，所以有 $\frac{3 \times 8}{2} = 12$ 条棱。

几何概率是一种计算概率的方法：用长度、面积或体积从几何上度量结果的“多少”。解几何概率题的关键是

1. 针对不同情况试几个例子，并且一定要标出极端情况。
2. 弄清楚这些结果在图上构成什么区域。
3. 用几何方法求出这块区域的面积。

期望值是所有结果的加权平均：每个结果按它发生的可能性大小占相应的比重。

随机量 $X$ 的期望值是

其中 $x_i$ 是 $X$ 所有可能的取值，$P(x_i)$ 是每个取值出现的概率。

用一句话说：把每个取值乘上它的概率，再加起来。

对于任意随机量 $x_1, x_2, \dots, x_n$，无论独立还是相关，都有

总和的期望值等于各部分期望值之和。

递推就是先求出较小的值，再用它们计算较大的值。

用递推解题分几步：

1. 自己动手解出几个较小的初始值。
2. 一般来说，递推式右边有几项，就需要几个初始值。
3. 对一般的 $f(n)$，看看到达这一步有哪些不同的方式，用前面的值写出递推式。
4. 一步一步计算 $f(n)$，直到算出你要的那个数。

很多时候，定义两个递推函数会更简单，比如 $a(n)$ 和 $b(n)$，真正的答案是两者的某种组合（例如 $a(n) + b(n)$）。

当我们想求从不同局面或不同轮次出发“获胜”的概率时，就用状态。解状态问题分三步：

1. 给从每个局面出发获胜的概率设一个未知数。
2. 对每个局面，用其他状态表示从它出发获胜的概率，写出一个方程。
3. 解这个方程组。

做状态问题时，一定要留意对称性：获胜概率相同的局面可以共用一个未知数。这样方程会简单得多。

对于状态递推，一个好办法往往是直接列一张表，写出每个时刻处于每个位置的概率。记住：每一步的概率总和必须始终为 $1$。

期望值状态的用法和概率状态几乎完全一样。唯一的区别：每个方程都要加 1。例如

之所以加 $1$，是因为从 $A$ 走到 $B$ 要花 $1$ 步。

对任意非零的 $x$：

如果

那么

平方差：

立方差：

立方和：

奇次幂之和：

第二个因式中的符号正负交替。

幂之差：

第二个因式中的符号全是正号。

SFFT：

1. 代入法
2. 消元法
3. 把方程相加、相减、相乘
4. 把项分组
5. 通分
6. 不一定要求出每一个未知数
7. 利用未知数之间的对称性
8. 巧妙换元，让式子变简单
9. 寻找常见的因式分解

二次方程

的解是

在求根公式中，

（根号里面的部分）叫作这个二次式的判别式。

1. 如果判别式 $b^2 - 4ac$ 等于 $0$，那么这个二次式有一个重根。
2. 如果判别式 $b^2 - 4ac$ 是正数，那么这个二次式有 2 个不同的实根。
3. 如果判别式 $b^2 - 4ac$ 是负数，那么这个二次式没有实根。

在二次方程

中，两根之和是

，两根之积是

对于多项式方程

设它的根为 $r_1, r_2, r_3, \dots, r_n$，则有：

符号正负交替：奇数个根之积的和带负号，偶数个根之积的和带正号。

多项式

可以写成

其中 $r_1, r_2, r_3, \ldots, r_n$ 是这个多项式的 $n$ 个根。

多项式

（首项系数是 $1$）可以写成

其中 $r_1, r_2, r_3, \ldots, r_n$ 是这个多项式的 $n$ 个根。

如果题目要求像 $(k - r)(k - s)(k - t)$ 这样的式子，其中 $r$、$s$、$t$ 是一个首一多项式 $P$ 的根，那么由上面的表示，它就是 $P(k)$。对于不是首一的多项式，方法一样，只是这个乘积等于

其中 $a_n$ 是 $x^n$ 项的系数。

一个 $n$ 次多项式（最高次项的次数是 $n$）在计入重数的情况下恰有 $n$ 个复数根。例如，一个重根算作 $2$ 个根。

多项式 $P(x)$ 除以 $x - r$ 的余数是 $P(r)$。

如果 $P(r) = 0$，那么 $x - r$ 整除多项式 $P(x)$。这是余数定理的直接推论。

如果多项式

满足

就称它是对称的。简单地说，首尾对应位置的系数相等。

要解一个偶数次的对称多项式 $P(x) = a_0 x^n + a_1 x^{n-1} + \cdots + a_1 x + a_0$：

• 除以 $x^{n/2}$。
• 把 $x^k$ 项和 $\frac{1}{x^k}$ 项放在一起。
• 换元

把式子中的每一项都用 $y$ 表示。

• 解出降次后的多项式。

如果

的根是 $r_1, r_2, r_3, \ldots, r_n$，那么

的根是

把一个多项式的系数倒过来排，它的根就变成原来各根的倒数。

如果

的根是 $r_1, r_2, r_3, \ldots, r_n$，那么

的根是

设 $P(x) = a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1 x + a_0$ 的根是 $r_1, r_2, \ldots, r_n$，并设

那么

依此类推。这里当 $j$ 为负数时 $a_j = 0$（$k > n$ 时会遇到这种情况）。

用文字说：

1. 用首项系数 $a_n$ 乘 $S_k$。
2. 用下一个系数 $a_{n-1}$ 乘 $S_{k-1}$，再用 $a_{n-2}$ 乘 $S_{k-2}$，依此类推，把这些乘积加起来。
3. 到 $S_0$ 时停下：不乘 $S_0$，而是把最后那个系数乘以 $k$。（如果系数先用完了，就直接停下。）
4. 令总和等于 $0$。

用文字表示：

代入 $a_n = a_1 + (n - 1)d$，得到

一般地，等比数列的各项可以记作

其中

• $r$ 是相邻两项的公比
• $n$ 是项数

通项公式：

当 $r \ne 1$ 时，

当 $-1 < r < 1$ 时，

简单地说，前 $n$ 个奇数之和是 $n^2$。

直观地想：把每一项里的 $2$ 提出来：

把开头几项和最后几项展开，把能抵消的项都消掉。

反过来写：$\text{总和} = \text{平均数} \times \text{项数}$。大多数平均数问题其实都是总和问题。

把这些数按从小到大（或从大到小）的顺序排好后：

• 如果项数是奇数，中位数就是正中间的那个数。
• 如果项数是偶数，中位数就是中间两个数的平均数。

正数 $a_1, a_2, a_3, \ldots, a_n$ 的几何平均数是

正数 $a_1, a_2, a_3, \ldots, a_n$ 的调和平均数是

用一句话说：倒数的平均数的倒数。

$a_1, a_2, a_3, \ldots, a_n$ 的平方平均数（均方根）是

对于正数，$\text{QM} \ge \text{AM} \ge \text{GM} \ge \text{HM}$，当且仅当所有数都相等时取等号（第 40 章会证明它）。

等价地，

如果一个人完成某件事需要 $a$ 单位的时间，另一个人完成同一件事需要 $b$ 单位的时间，那么两人合作完成需要

单位的时间。

等价地，

单位要对应：每小时多少英里，就要配上以小时为单位的时间。先把分钟换算好。

质数是恰好有两个因数的数：$1$ 和它本身。例如，$2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots$ 都是质数。

质因数分解就是把一个数写成若干个质数的乘积。

例：$60$ 的质因数分解是 $2^2 \times 3 \times 5$。

如果一个数的质因数分解是

那么这个数的因数个数是

如果一个数的质因数分解是

那么这个数所有因数的和是

对质因数分解中的每个质数 $p$，先求出 $p^k$ 对所有可能的指数 $k$（从 $0$ 到 $p$ 的指数）的和。再把所有质数对应的这些和乘起来，就得到这个数所有因数的和。

如果一个数 $n$ 有 $f$ 个因数（用因数个数公式数出来），那么 $n$ 的所有因数的积是

对于质数 $p$，$n!$ 中因数 $p$ 的个数是

一旦 $p^k > n$，求和就停止，因为后面的每一项都是 $0$。

两个或多个非零整数的最大公因数（GCD），是能整除其中每一个数的最大正整数。

它也叫最大公约数（英文也写作 GCF，即 Greatest Common Factor）。这两种叫法意思相同。

两个或多个非零整数的最小公倍数（LCM），是能被其中每一个数整除的最小正整数。

在 $m$ 和 $n$ 的质因数分解中，$\gcd(m, n)$ 对每个质因数取较低的指数。

$\operatorname{lcm}(m, n)$ 对每个质因数取较高的指数。

例如，$24 = 2^{3} \cdot 3$，$36 = 2^{2} \cdot 3^{2}$，所以 $\gcd(24, 36) = 2^{2} \cdot 3 = 12$，$\operatorname{lcm}(24, 36) = 2^{3} \cdot 3^{2} = 72$。

两个数的最大公因数与最小公倍数之积，等于这两个数之积：

如果两个数有公因数 $c$，那么

其中 $x > y$，$k$ 是正整数。

方程

有整数解 $x, y$，当且仅当 $\gcd(a, b)$ 整除 $c$。

表示数 $n$ 和 $a$ 除以 $b$ 的余数相同。等价地说，$b$ 整除 $n - a$。读作“$n$ 与 $a$ 模 $b$ 同余”。

若 $a \equiv x \pmod{n}$ 且 $b \equiv y \pmod{n}$，则

（原书把第一个同余式印成了“$a = x \pmod n$”，意思是 $\equiv$。）

若 $a \equiv x \pmod{n}$，则对每个正整数 $m$，都有

要求一个很大的幂 $a^b$ 的末一位（或末几位）数字，先算出 $a^b$ 的前几个值，找出规律。余数最终一定会重复，所以这个规律可以推广到很大的 $b$。

若 $n$ 的质因数分解是 $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$，则

其中 $\varphi(n)$ 是不超过 $n$ 且与 $n$ 互质的正整数的个数。

步骤： 1. 求出 $n$ 的质因数分解。2. 对每个质数 $p_i$，写出 $1 - \frac{1}{p_i}$，并把它们相乘。3. 再把这个积乘以 $n$。

对 $n > 1$，

成立当且仅当 $\gcd(a, n) = 1$。

若 $p$ 是质数且 $p \nmid a$，则

（原书写的是“当且仅当 $p$ 是质数且 $\gcd(a, n) = 1$”。逆命题是错的：$561 = 3 \cdot 11 \cdot 17$ 不是质数，但对每个与 $561$ 互质的 $a$，都有 $a^{560} \equiv 1 \pmod{561}$。）

若 $ab \equiv 1 \pmod{n}$，则 $a$ 是 $b$（模 $n$）的模逆元，$b$ 也是 $a$ 的逆元。记作

$a$ 的逆元存在，当且仅当 $\gcd(a, n) = 1$。

对质数 $p$，

对非负整数 $n$，

在模运算中，把大的底数写成“小数 + 10 的倍数”：在 $(1 + 10)^{n}$ 中，从 $10^3$ 开始的每一项模 $1000$ 都是 0，所以 $(1 + 10)^n \equiv 1 + 10n + 100\binom{n}{2} \pmod{1000}$。

若正整数 $x$ 满足

其中 $n_i$ 两两互质，则 $x$ 模 $n_1 n_2 \cdots n_k$ 有唯一解。

解两个同余式组成的方程组，可以尝试检验，直到找到同时满足两个条件的数；也可以用代数方法：

1. 从 $n \equiv r_1 \pmod{m_1}$ 和 $n \equiv r_2 \pmod{m_2}$ 出发，其中 $m_1$ 与 $m_2$ 互质。
2. 把第一个改写成等式：$n = k m_1 + r_1$。
3. 代入第二个：$k m_1 + r_1 \equiv r_2 \pmod{m_2}$，所以 $k \equiv (r_2 - r_1)\cdot m_1^{-1} \pmod{m_2}$。
4. 用尝试检验求出 $m_1^{-1} \pmod{m_2}$。
5. 现在知道 $k \equiv k_0 \pmod{m_2}$；写成 $k = m_2 t + k_0$。
6. 代回 $n = k m_1 + r_1$。
7. 读出最后的同余式 $n \equiv k_0 m_1 + r_1 \pmod{m_1 m_2}$。