课堂内容 后缀数组 后缀数组主要指两个数组 $sa$ 和 $rank$： $sa_i$ 表示所有后缀中按字典序大小从小到大排序后排名为 $i$ 的后缀的起始位置。 $rank_i$ 表示以 $i$ 为起始位置的后缀的排名。 其中这两个数组有如下性质： $$ sa_{rank_i} = rank_{sa_i} = i $$ 可以使用倍增 + 基数排序的方式求解 $sa$ 和 $rank$ 数组，复杂度 $O(n \log n)$。 除此之外，还有一个 $height$ 数组表示 $sa_i$ 和 $sa_{i-1}$ 两个后缀的 LCP (Longest Commo...

Luogu-P13270 最小表示法 题意 给定一个长度为 $n$ 的字符串 $s$，求 $s$ 的最小表示法。 思路 首先如果暴力的话，复杂度是 $O(n^2)$ 的，但是我们发现如果我们当前已经发现了一个最小表示法，我们想要找到一个比这个还小的表示法，那么一定存在一个位置，使得这个位置上的字符不相等，根据这个就可以把复杂度优化到 $O(n)$。 提交记录：Link。 [Luogu-P5...

课堂内容 字符串哈希 定义哈希函数 $H(s)$: $$ H(s) = \sum_{i=1}^n base^{n-i} s_i \bmod P $$ 其中 $base$ 大于字符集大小。这个哈希函数的冲突概率为 $\frac{1}{P}$。 通过这个定义，我们可以通过前缀和处理，得到这个字符串上每个区间的哈希值。 树哈希 （重点） 定义哈希函数 $H(u)$，表示以 $u$ 为根节点的子树的哈希值。 $$ H(u) = \sum_{i} H(son(u, i))^{1 + \sum_{j<i} 2 \times size(son(u, j))} + 1 ...

# 内容 休息一天喵o(〃＾▽＾〃)o~

课堂内容 完全图匹配构造 描述 对于一个 $n$ （$n \mid 2$） 个顶点的完全图，将其分为 $n-1$ 个匹配。 思路 我们将其中一个点提出来，剩下的 $n-1$ 个点形成一个正多边形，然后将提出的那个点放在中心。 对于每一条 “斜率” 相同的边，我们把他们放在一个方案中，然后对这个方案进行旋转，就构造了 $n-1$ 个匹配。 img 完全图曼哈顿路构造 描述 对于一个包含 $n...

Content：博弈论 Date：2025.8.2 课堂内容 SG 函数 表示当前游戏局面的函数，后手必胜当且仅当 SG 函数为 0。 多个游戏的组合的 SG 函数为每个游戏的 SG 函数的 异或和。 经典模型 取石子游戏 题目描述 有 $n$ 堆石子，A、B 轮流取，每次从任意一堆中取出至少一个石子，不能取的输，问谁赢。 解法 一堆大小为 $n$ 的 SG 函数为 $n$，根据 SG 函数的性质，可以发现整个游戏的 SG 函数为 $\displaystyle \bigotimes_{i=1}^n S...

Content：生成函数，多项式，期望 Date：2025.8.1 课堂内容 生成函数 定义 普通生成函数（OGF）：普通生成函数的定义为形式幂级数：$\displaystyle F(x) = \sum_{i} a_i x^i$ 指数生成函数（EGF）：指数生成函数的定义为形式幂级数：$\displaystyle F(x) = \sum_{i} a_i \frac{x^i}{i!}$ 普通生成函数的基本运算 $\displaystyle F(x) \pm G(x) = \sum_{i} (a_i \pm b_i...

Content：组合数学 Date：2025.7.31 课堂内容 容斥原理 其主要思想为：把禁止违反哪些规则改为钦定违反了哪几条规则，并赋予 $(-1)^k$ （即违反 $k$ 条规则）的容斥系数。 二项式反演 $$ \begin{aligned} g(n) &= \sum_{i=0}^n \binom{n}{i} f(i) \Leftrightarrow f(n) = \sum_{i=0}^n (-1)^{n-i} \binom{n}{i} g(i) \\ g(n) &= \sum_{i=n}^N \binom{i}{n} f(i) \Left...

Content：数论 Date：2025.7.30 课堂内容 莫比乌斯函数 定义如下： $$ \mu(n) = \begin{cases} 1 & n=1 \\ (-1)^k & n = p_1 p_2 p_3 \dots p_k, \forall p_i \in P \\ 0 & otherwise \\ \end{cases} $$ 其中莫比乌斯函数有如下性质： $$ \sum_{d|n} \mu(d) = [n=1] $$ 欧拉函数 定义如下： $$ \varphi(n) = \sum_{i=1}^n [gcd(n,i)=1] $...

Content：平衡树 Date：2025.7.29 具体内容 Leafy Tree 和 Un-leafy Tree Leafy Tree：表示将所有的数据存放在叶子节点的树形数据结构，类似 线段树 和 WBLT 平衡树。 Un-leafy Tree：与 Leafy Tree 相反，将数据存放在每个树节点的数据结构。 替罪羊树 替罪羊树是最简单的平衡树，也是 Un-leafy 的，其核心思想是定义一个常数 $\alpha$，对于树上任意节点 $u$，若 $\max(siz_{ls_{u}}, siz_{rs_{u}...