排序算法

	平均	最好	最坏	辅助空间	稳定性	概述
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$T(1)$	稳定	扫一遍移动当前已知最大元素与下一元素交换
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$T(1)$	不稳定	第 $i$ 次选择剩余最大值与第 $i$ 个元素换位
插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$T(1)$	稳定	拿出当前元素，挨个尝试往前放置找到合适位置
希尔排序		$O(n)$		$T(1)$	不稳定	步长从 $\frac{n}{2}$ 到 $1$ 进行直接插入排序
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$T(n)$	稳定	递归将左右两个已经排序的序列合并成一个序列
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$T(\log n)\sim T(n)$	不稳定	选择基准值后分段递归处理。具体就是用两个指针扫，二者都不合法就交换，直到相遇
计数排序	$O(n+V)$	$O(n+V)$	$O(n+V)$	$T(n+V)$	稳定	丢到桶里，求桶的前缀和，按原序列倒序分配排名保证稳定性
基数排序	$O(kn+\sum V_i)$	$O(kn+\sum V_i)$	$O(kn+\sum V_i)$	$T(n+k)$	稳定	从低位到高位逐一做稳定排序，一般结合计数排序

其中，『稳定性』是指：若两元素大小相等，排序前后两元素相对位置不变，则称该排序算法稳定。

数学杂项

阶乘

\ln n!\approx n\ln n

康托展开 / 变进制数

给定变进制数，求其排名。公式为： $1+\sum\limits_{i=1}^nA_i\times(n-i)!$ ，其中 $A_i$ 表示在 $i$ 右侧的比 $a_i$ 小的数的个数。用树状数组维护一下前（后）缀和。时间复杂度 $O(n\log n)$ 。

理解：模板题题解。其实就是对于每个位置考虑如果 $i$ 前面每个位置都一样，到第 $i$ 位开始出现区别有多少种排列。所以是 $i$ 位能放的小于 $a_i$ 的数的个数乘一个排列数。

逆康托展开就 $-1$ 之后每次除一下阶乘（ $n!\rightarrow1!$ ），依次商就是 $A_i$ ，余数重复操作。得到 $A_i$ 就依次尝试填一下。权值线段树 + 二分做到 $O(n\log n)$ ，树状数组 + 倍增是 $O(n\log^2n)$ 但是常数小。

同底数取模快速幂

$a^b=a^{b\bmod s}\times a^{\lfloor\frac bs\rfloor}$ ，其中 $s$ 取 $\sqrt p+1$ 。预处理复杂度 $O(\sqrt p)$ ，询问 $O(1)$ 。

平方和、立方和公式

平方和公式： $\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}6$ 。

立方和公式： $\sum_{i=1}^n i^3=\frac{n^2(n+1)^2}4$ 。

距离表示方法

欧几里得距离

点 $A(x_1,y_1)$ 与点 $B(x_2,y_2)$ 的距离 $|AB|=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$ 。

曼哈顿距离

点 $A(x_1,y_1)$ 与点 $B(x_2,y_2)$ 的距离 $|AB|=|x_1-x_2|+|y_1-y_2|$ 。

切比雪夫距离

点 $A(x_1,y_1)$ 与点 $B(x_2,y_2)$ 的距离 $|AB|=\max\{|x_1-x_2|,|y_1-y_2|\}$ 。

曼哈顿距离与切比雪夫距离的互相转化

原坐标系中的点 $(x,y)$ 变换成新坐标系中的点 $(x+y,x-y)$ ，原坐标系的曼哈顿距离 $=$ 新坐标系的切比雪夫距离。

原坐标系中的点 $(x,y)$ 变换成新坐标系中的点 $(\frac{x+y}2,\frac{x-y}2)$ ，原坐标系的切比雪夫距离 $=$ 新坐标系的曼哈顿距离。

博弈论

博弈图

无后继的状态为必败态。
必胜态有至少一个后继必败。
必败态所有后继必胜。

如果博弈图是一个 DAG，则在绘出博弈图的情况下用 $O(N+M)$ 的时间得出每个状态是必胜状态还是必败状态。

Nim 游戏与 Nim 和

Nim 游戏： $n$ 堆物品，每堆有 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，不能不取。没有物品取的玩家判负。

Nim 和：定义 Nim 和 $=a_1\oplus a_2\oplus\cdots\oplus a_n$ 。当且仅当 Nim 和为 $0$ 时，该状态为必败态；否则该状态为必胜态。

有向图游戏与 SG 函数

有向图游戏：DAG 的起点上有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。

SG 函数： $\text{SG}(x)=\text{mex}\{\text{SG}(y_1),\text{SG}(y_2),\cdots,\text{SG}(y_n)\}$ ，其中 $\{y_i\}$ 是 $x$ 的后继。约定终止态的 $\text{SG}$ 值为 $0$ 。当且仅当 $\text{SG}$ 和为 $0$ 时，该状态为必败态；否则该状态为必胜态。