主要考察点分为五个部分：倍增、最短路、最小生成树、数论和组合数学。
倍增
倍增，就是成倍增长。在线性递推超时的时候，我们可以只获取在 k 的整数次幂位置上的值。当需要其他位置上的值时，我们通过 '任意整数可以被分为若干个 k 的次幂项的和' 这一性质，使用获取过的值来得到想要求到的值。 倍增有三大应用场面，分别是 快速幂、LCA、RMQ，快速幂不常考。
倍增 LCA
LCA（Lowest Common Ancestor)为树上算法，意为 最近公共祖先。定义：若干个点的公共祖先中离根 最远 的点就叫这些点的最近公共祖先。
例如下图中，4 和 6 的最近公共祖先是 2；2、4、6 的最近公共祖先是 2。
在 LCA 中，我们可以用 p[x][i] 表示 x 的第 2^i 个祖先，p[x][0] 就是 x 的父亲，p[x][i] 就是 x 的第 2^{i-1} 个祖先的第 2^{i-1} 个祖先。
同时我们维护数组 dep，dep[i] 表示 i 离根的距离。
我们可以通过 dfs 求出 p 数组和 dep 数组。
先给出 预处理 的 dfs 代码：
void dfs(int now, int fa) {
dep[now] = dep[fa] + 1;
p[now][0] = fa;
for (int i = 1; i <= 20; ++i) p[now][i] = p[p[now][i-1]][i-1]; // i=[1,20]，核心
for(auto node : edge[now]) if(node != fa) dfs(node, now);
}
现在我们着重考虑 2 个点的 LCA。首先，我们检查 dep_x >= dep_y，若不满足，则交换 x, y。接着，我们让 x 通过跳跃到达 y 的所在层数。这时，如果我们发现 x == y，则直接返回 x；否则两个点同时往上跳跃，直到 p[x][0] = p[y][0]，最后返回 p[x][0] 即可。
LCA 函数：
int lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for (int i = 20; i >= 0; --i) if(dep[p[x][i]] >= dep[y]) x = p[x][i];
if(x == y) return x;
for (int i = 20; i >= 0; --i) if(p[x][i] != p[y][i]) x = p[x][i], y = p[y][i];
return p[x][0];
}
建议尝试练习洛谷 P3379。
数论与组合数学
计数原理
加法计数原理
完成一件事，有 n 类办法，每类办法 互相独立。
- 第一类有 m1 种方法；
- 第二类有 m2 种方法；
- 第三类有 m3 种方法；
- ……
- 第 n 类有 mn 种方法。
即总方法数是 m1 + m2 + m3 + ⋯ + mn。 关键词：分类、任选其一、互不干扰。
乘法计数原理
完成一件事，需要分成 n 个步骤，步骤之间 有先后顺序。
- 第一步有 m1 种方法；
- 第二步有 m2 种方法；
- 第三步有 m3 种方法；
- ……
- 第 n 步有 mn 种方法。
即总方法数是 m1 × m2 × m3 × ⋯ × mn。 关键词：分步、缺一不可、先后顺序。
区分方法
能 一步 做完 → 分类 → 加法 → '或'。 必须 多步 做完 → 分步 → 乘法 → '且'、'先……再……' 。
阶乘
n! = ∏_{i=1}^{n} i = n × (n-1) × (n-2) × ⋯ × 2 × 1，注意 0! = 1。
排列
从 n 个不同元素中，有序 取出 m 个排成一列，叫排列，通常记作 A_n^m 或 P_n^m。
A_n^m = n! / (n-m)! = ∏_{i=n-m+1}^{n} i。
全排列：A_n^n = n!
组合
从 n 个不同元素中，无序 取出 m 个组成一组，叫组合，通常记作 C_n^m 或 \binom{n}{m}。
C_n^m = A_n^m / m! = n! / (m!(n-m)!). 性质：
- C_n^m = C_n^{n-m}（对称性）；
- C_n^0 = C_n^n = 1；
- C_n^m + C_n^{m+1} = C_{n+1}^{m+1}（杨辉三角）；
- ∑_{i=0}^{n} C_n^i = 2^n。
鸽巢原理（抽屉原理）
基本形式
把 n+1 个物体放入 n 个抽屉中，则 至少有一个抽屉 里包含 至少两个 物体。
推广形式
把 km+1 个物体放入 k 个抽屉中，则至少有一个抽屉里包含至少 m+1 个物体。
典型应用
- 任意 13 个人中，至少有 2 个人的生日在同一个月；
- 任意 5 个整数中，至少有 3 个整数的和是 3 的倍数。
卡特兰数
定义
第 n 个卡特兰数记作 Catalan(n)，公式为： Catalan(n) = 1/(n+1) * C_{2n}^n = (2n)! / ((n+1)! * n!)。
初始值
Catalan(0) = 1，Catalan(1) = 1，Catalan(2) = 2，Catalan(3) = 5，Catalan(4) = 14。
典型应用场景
- 合法括号匹配的数量：n 对括号的合法组合数为 Catalan(n)；
- 出栈序列的数量：n 个元素进栈后，合法出栈序列数为 Catalan(n)；
- 凸多边形三角剖分：n 边形的三角剖分方案数为 Catalan(n-2)。
