《ACM国际大学生程序设计竞赛 知识与入门》

第3章 数学基础

3.1 函数增长与复杂性分类

为算法复杂性定义了几种符号:

1. $\Theta$记号: $\Theta(g) := 0 \leqslant c_1 g \leqslant f \leqslant c_2 g$, 其中 $c_1, c_2$ 为常数.
2. $O$记号: $O(g) := 0 \leqslant f \leqslant cg$, 其中 $c$ 为常数.
3. $o$记号: $o(g) := 0 \leqslant f < cg$, 其中 $c$ 为常数.
4. $\Omega$记号: $\Omega(g) := 0 \leqslant cg \leqslant f$, 其中 $c$ 为常数.
5. $\omega$记号: $\omega(g) := 0 \leqslant cg < f$, 其中 $c$ 为常数.

常见的阶:

$$c < \log n < n < n \log n < n^a < a^n < n! < n^n$$

Church-Turing thesis: 任何可有效演算的函数都是可计算的函数.
其中可有效演算意为"直觉上认为可计算的"，可计算意为"切实可被机器计算的".

3.3 代数学

3.3.1 矩阵

矩阵乘法的作用: 递推可以表示成向量乘以矩阵，然后可用快速幂优化.
例如计算 Fibnacci 数列时, 将 $a_0=0, a_1=1, \cdots , an = a{n-1} + a_{n-2}$ 表示成为

$$
\binom{a_{n+1}}{a_n} = \binom{an+a{n-1}}{a_n+0} =
\begin{pmatrix}
1 & 1 \
1 & 0
\end{pmatrix}
\binom{an}{a{n-1}}=
\begin{pmatrix}
1 & 1 \
1 & 0
\end{pmatrix}^n
\binom{a_1}{a_0}
$$

若记 $A=\begin{pmatrix}1&1\1&0\end{pmatrix}$, 则有 $\displaystyle\binom{an}{a{n-1}}=A^n\binom{1}{0}$

3.3.5 复数

复数乘法

复数除法

3.3.6 群论

群作用: 对于集合 $S$, 总会有一些从 $S$ 到 $S$ 的双射置换 $e,g,h$, 使得

1. $e \circ x = x, \forall x \in S$. (封闭性)
2. $(gh) \circ x = g \circ ( h \circ x ), \forall x \in S$. (结合性)

这些 $e,g,h$ 所构成的置换群 $G$ 是在 $S$ 上的一个群作用.
轨道: 对于群作用中给出的概念, $x \in S$, 由 $x$ 经群 $G$ 中所有置换作用导出的 $x' \in S$ 组成的集合, 称为 $x$ 的轨道.
稳定子: 能让 $x \in G$ 经 $g$ 置后保持不变的所有 $g$ 的集合称为 $x$ 在 $G$ 中的稳定子.

3.4 组合学

3.4.2 鸽巢原理

广义鸽巢原理: 有 $q_1, q_2, \cdots, q_n$ 这些正整数。如果将: $q_1+q_2+\cdots+q_n-n+1$ 个物体放入 $n$ 个盒子, 那么至少存在 $1 \leqslant k \leqslant n$, 使得第 $k$ 个盒子里有 $q_k$ 个物体.

3.4.3 容斥原理

错位排列: 记 $A_i$ 表示第 $i$ 位不错位，则所有错位排列 $D_n=|\bar A_1 \cap \bar A_2 \cap \cdots \cap \bar A_n |$

3.4.4 特殊计数序列

Catalan 序列
$$C_n=\frac{1}{n+1}\binom{2n}{n}$$
应用:

1. $n$ 对括号构成的合法括号序列个数等于第 $n$ 个 Catalan 数.
2. 通过不相交于内部的对角线把凸 $n+2$ 边形拆分成若干个三角形, 不同的拆分方法数等于第 $n$ 个 Catalan 数.

Stirling 数

1. $s(p,k)$ 是将 $p$ 个有区别的球排成 $k$ 个非空个圆排列的方案数.
2. $S(p,k)$ 是将 $p$ 个有区别的球放到 $k$ 个相同的盒子中(没有空盒)的方案数.

$$
s(p,k) = (p-1) s(p-1,k) + s(p-1,k-1) \
S(p,k) = S(p-1,k) + S(p-1,k-1)
$$

3.4.5 Pólya 计数定理

对于具有 $n$ 个元素的排列 $a_1 a_2 \cdots a_n$, 在置换 $f=
\begin{pmatrix}
1 & 2 & \cdots & n \
a_1 & a_2 & \cdots & a_n
\end{pmatrix}$ 的作用下可变为其他排列.
对于排列集合 $C$ 和置换群 $G$ 而言, 有:

1. $\forall g \in G, \forall c \in C, g \circ c \in C$.
2. $\exists 1_g \in G, \forall c \in C, 1_g \circ c \in C$.
3. $\forall g,h \in G, \forall c \in C, (g \circ h) \circ c = g \circ ( h \circ c )$.

等价关系: $\exists c_1,c_2 \in C, \exists g \in G, g \circ C_1 = C_2,$ 此时记 $c_1 \mbox{~} c_2$.

3.6 数论

3.6.1 整除

Pollard's ρ 算法 求因数分解

• Input: $n$
• Output: $d | n$
  1. $x$ 是 $(2,n-1)$ 间的随机数
  2. $y \leftarrow x, k \leftarrow 2, i \leftarrow 1$
  3. 重复以下过程
     3.1. $i \leftarrow i + 1$
     3.2. $x \leftarrow x^2 - 1 \pmod n$ (或其他伪随机生成算法)
     3.3. $d \leftarrow (|y-x|,n)$
     3.4. 若 $1<d<n$, 返回 $d$
     3.5. 若 $i=k$, 令 $y \leftarrow x, k \leftarrow 2k$

3.6.2 不定方程

变量数多于方程数, 只考虑整数解的方程.
二元一次否定方程 $ax+by=c$ 有解的充要条件是 $(a,b)|c$, 因为满足该条件的方程总可化为 $a'x+b'y=c'$ 的形式, 其中 $(a',b')=1$.
此方程可用扩展 Euclid 算法求解.

3.6.3 同余方程与欧拉定理

Euler定理: $(a,m)=1$, 则有 $a^{\varphi(m)} \equiv 1 \pmod m$.
Euler函数: $\displaystyle \varphi(n)=n\prod_{p|n}(1-\frac{1}{p})$, ( $p$ 是素数, 计重数 ).
$\varphi(n)$ 等于 $1$ ~ $n-1$ 中与 $n$ 互素数的个数.
孙子定理: $m_1, \cdots, m_k$ 两两互素, 方程组 $x \equiv a_i \pmod{mi}$ 的解为
$$
x \equiv \sum{i=1}^k M_i M_i^{-1}a_i \pmod{m_i}
$$
其中, $\displaystyle m=m_1m_2\cdots m_k, M_i=\frac{m}{m_i}, M_i^{-1}M_i \equiv 1 \pmod{m_i}$.

Miller-Rabin素数测试

• Input: 待测大奇数 $n$, 控制准确度的正整数 $k$
• Output: 是否为素数
  1. 求 $d$, 使 $n-1 = 2^sd$
  2. 重复下列过程 $n$ 次
  3. $a$ 取 $1$ ~ $n-1$ 间的随机数
  4. $x \leftarrow a^d \pmod n$
  5. 重复下列过程 $s$ 次
     1. $x' \leftarrow x^2 \pmod n$
     2. 若 $x \neq \pm 1$ 且 $x' = 1$, 返回合数
     3. $x \leftarrow x'$
  6. 若 $x \neq 1$, 返回合数
  7. 返回素数

3.6.4 原根、离散对数和二项同余方程

指数: $(a,m)=1$, 能使 $a^d \equiv 1 \pmod m$ 成立最小的 $d$ 称为 $a$ 对模 $m$ 的指数, 记作 $\delta_m(a)$.
若 $\delta_m(a) = \varphi(m)$, 称 $a$ 是 $m$ 的原根.
模 $m$ 有原根的充要条件是 $m = 1, 2, 4, p^\alpha, 2p^\alpha$, 其中 $p$ 是奇素数.

第4章 数据结构

4.2.2 并查集

Ackerman 函数, Kruskal 函数.

第5章 图论

5.1 图

诱导子图, 环, 匹配, 覆盖, 团, 独立集, 支配集, 二染色, 正则图, 弦图, 竞赛图, 割点, 桥, 2-SAT

5.1.5.1 哈密顿路

哈密顿路: 一个图上恰好每个顶点都经过一次的路径.
哈密顿环: 经过每个顶点一次而且回到起点的路径.

5.1.5.2 欧拉路

欧拉路径: 图上存在一条路径, 满足第一条边正好经过一次. (一笔画)
欧拉回路: 起点终点生命的欧拉路径.

• 欧拉回路的充要条件:
  • 有向图: 弱连通且所有顶点的总入度等于总出度.
  • 无向图: 连通且所有顶点度为偶数.
• 欧拉路径的充要条件:
  • 有向图: 弱连通, 除两个顶点以外, 其他所有顶点的入度等于出度, 且此两个顶点中, 一个入度比出度多1, 另一个出度比入度多1.
  • 无向图: 连通, 除两点外, 其他顶点度为偶数.

5.1.6 最短路

5.1.6.1 Bellman-ford 算法

用来计算图中单源最短路.

5.1.6.2 Dijkstra 算法

用来解决非负边权图的单源最短路问题.

• Input: 图$G$和起点$S$.
• Output: $S$到每个点的最短路径.
  1. 初始化距离数组
  2. 设置所有点未访问
  3. 重复下列过程
     3.1. 找出所有未访问的点中距离最小的点, 标记为访问过
     3.2. 对上步中找到的点的相临边进行松弛

5.1.6.3 Floyd 算法

用以计算带权图中多源最短路问题, 使用动态规划原理.

5.2 树

树未必有根.普通树的任一点被选为根后, 即成为有根树.
中心: 不断将树中度为1的点删除, 重复操作直到最后剩下一个或两个点, 称为树的中心.

5.2.2 生成树

生成树是连通原图所有顶点边数最少的子图, 是不包含环的边数最多的子图.
计算生成树有 Prim 算法和 Kruskal 算法.

生成树计数

有关概念: Prüfer 编码, 表示图.
拉普拉斯矩阵（基尔霍夫矩阵）: 将图中点编号为 $1$ ~ $n$, 对于点 $i$, 点 $j$, 定义: $L=(l{i,j}){nn}$,其中:
$$
\begin{equation}
l_{i,j}=
\begin{cases}
\deg(v_i) &\mbox{if $i=j$} \
-1 &\mbox{if $i \neq j$, 点 $i$ 与点 $j$ 相临} \
0 &\mbox{其他情况}
\end{cases}
\end{equation*}
$$
基尔霍夫定理: 生成数个数$\displaystyle t(G)=\frac{1}{n}\lambda_1 \lambda_2 \cdots \lambda_s$$, 其中$\lambda_i$为$L$的非零特征值.

第6章 计算几何

6.1 向量

疑问: 四维向量叉积怎么算?

6.2 点的有序化

对一个无序点集进行排序，使之成为简单多边形的过程。
极角序: 选一个点作为极点, 从极点张开极坐标系. 其余点在该坐标系中的角度称为极角. 将极点按极角从小到大排序. 对于极角相同的点, 如果这两个点的极角不比其他所有点小, 则将与极点距离大的排在前, 否则将与极点距离小的点排在前.
水平序:

6.3 多边形与图

多边形面积
$$
S = \sum_i \frac{|\overrightarrow{OPi} \times \overrightarrow{OP{i+1}}|}{2}
$$
多边形重心
将多边形进行三角形剖分, 计算每个三角形的重心, 再将重心以每个三角形的面积为权重进行加权平均.
$$
\overrightarrow{C_i} = \frac{\overrightarrow{O} + \overrightarrow{Pi} + \overrightarrow{P{i+1}}}{3} \
\overrightarrow{C} = \sum_i \frac{(\overrightarrow{OPi}\times\overrightarrow{OP{i+1}})\cdot\overrightarrow{C_i}}{S}
$$

6.3.2 凸包问题

Graham 算法, 滚包裹法.

6.4 半平面交

半平面交一定是一个凸多边形. 任何一个凸包都能表示为$n$个半平面交.