部分懒得写了基于LLM自动补全的, 其实有点问题, 待改正

Kruskal 重构树

在跑Kruskal的同时维护并查集集合的来源,并储存为一个二叉树

具体步骤如下:

合并集合A,B的时候(对应加边), 新建一个节点, 它的左右儿子分别是A,B的根节点, 并将A,B的根节点的父亲设为这个节点, 同时将该点点权设为边权

性质:

两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值

用于解决一些边权约束问题

欧拉降幂

用于快速计算$a^{b}modm$ 的值 $(b$ 很大)｡核心思想：

1. 当 $gcd(a,m)=1$ 时，利用欧拉定理 $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$ 将指数对 $\phi (m)$ 取模降幂。
2. 若不互质，则需递归处理：在递归深度较大时给指数加上 $\phi (m)$ 以保持正确结果。

摩尔投票

用于在线求数组中出现次数超过一半的元素（多数元素）。

1. 维护候选值 cand 与计数器 cnt (初始无候选)。
2. 遍历序列： • cnt==0 时令 cand=val,cnt=1； • 否则：若 val==cand，cnt++；反之 cnt--。
3. 第二次遍历确认 cand 频数是否 > ⌊n/2⌋。

时间 $O(n)$，空间 $O(1)$。可扩展到找出现次数 > ⌊n/k⌋ 的元素（维护 $k-1$ 个候选）。

Pick 定理

对顶点均为整数点的简单多边形，有

$$A=i+\frac{b}{2}-1$$

其中 $A$：面积，$i$：内部格点数，$b$：边界格点数。常见用法：

1. 叉积求 $2A$。
2. $b$ 由各边 $gcd(|\mathrm{\Delta }x|,|\mathrm{\Delta }y|)$ 求和。
3. 由公式可转化求未知量（多为 $i$ 或 $A$）。

曼哈顿与切比雪夫

坐标旋转变换：令

$$(x^{\prime },y^{\prime })=(\frac{x+y}{2},\frac{x-y}{2})$$

则曼哈顿距离 $|x_1-x_2|+|y_1-y_2|$ 转化为切比雪夫距离 $max(|x_1^{\prime }-x_2^{\prime }|,|y_1^{\prime }-y_2^{\prime }|)$。 常见用途：最近/最远曼哈顿距离、菱形转正方形后用二维 ST-Table 或前缀和优化。

SG定理

无偏博弈（先手必败/必胜）判定：每个状态 $s$ 定义 SG 值

$$SG(s)=\mathrm{mex}\{SG(s^{\prime })\mid s^{\prime }\text{ 为 }s\text{ 的可达后继}\}.$$

结论：若初始局面 SG=0 则后手必胜，否则先手必胜。 性质与应用：

• 多堆异或和定律：若游戏可分解为子局面，则整体 SG 为各子局面 SG 的异或。
• 积木拿取、火柴棒游戏、树上删边等。

卡特兰数

$C_n={\displaystyle \frac{1}{n+1}}(\genfrac{}{}{0ex}{}{2n}{n})$ ($n\ge 0$)。 等价递推：$C_0=1,C_{n+1}=\sum _{i=0}^n{C}_i{C}_{n-i}$。 经典计数模型：

• $n$ 对括号的合法序列数
• $n+1$ 个叶子的满二叉树数
• 栈的 $n$ 元素进出序列数
• 圆内互不相交的 $n$ 条弦的连接方案数 常见做法：预处理逆元 + 阶乘表快速出组合数。

斯特林数

第一类斯特林数 $\left[\begin{array}{c}n\\ k\end{array}\right]$：将 $n$ 个不同元素排列成 $k$ 个非空循环的方案数；递推

$$\left[\begin{array}{c}n\\ k\end{array}\right]=\left[\begin{array}{c}n-1\\ k-1\end{array}\right]+(n-1)\left[\begin{array}{c}n-1\\ k\end{array}\right].$$

第二类斯特林数 $\left\{\begin{array}{c}n\\ k\end{array}\right\}$：将 $n$ 个不同元素划分为 $k$ 个非空子集的方案数；递推

$$\left\{\begin{array}{c}n\\ k\end{array}\right\}=\left\{\begin{array}{c}n-1\\ k-1\end{array}\right\}+k\left\{\begin{array}{c}n-1\\ k\end{array}\right\}.$$

常用板子：预处理三角表或用多项式插值 + 快速幂。

容斥

计算多个集合并集大小：

$$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{i=1}^n|A_i|-\sum _{1\le i<j\le n}|A_i\cap A_j|+\sum _{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|-\cdots .$$

步骤：状态压缩枚举子集, 奇加偶减；复杂度 $O(3^n)$ 可配合质因数分解或子集 DP 优化至 $O(n{2}^n)$。 常用场景：错排、求与 n 互素数个数、概率补集转化等。