丢番图方程
Codeforces 1013E
曼哈顿最小生成树
CSA Round 84 The Sprawl
条件期望
条件概率是条件期望的特例。
$E(X|A)$：「在事件 $A$ 发生的条件下」随机变量 $X$ 的期望。
全期望公式
设 $A_1, A_2, dots, A_i, dots$ 是样本空间的一个划分。
则有
$E(X) = sum_i E(X|A_i) Pr(A_i)$
离散随机变量 $X,Y$
$E(X|Y = y) = sum_{omega colon Y(omega) = y} E(X|omega)$
字符串哈希
对于字符串 $S$，将 $S$ 从右到左第 $i$ 个字符的权重置为 $p^i$，求和后对 $q$ 取模，模数即为字符串的哈希值。
也就是把字符串看作一个 $p$ 进制整数。
$p$ 通常是一个较小的质数，如 131，257，313
$q$ 通常是一个较大的质数，如 $10^9 + 7$
与正整数的 $p$ 进制表示相同，字符串哈希也采用「左边是高位，右边是低位」的方法。
这样做有两个好处：
- 便于采用秦九韶算法求字符串的哈希值
- 用子串 $S[i, i+l)$ 的哈希值，可以 $O(1)$ 算出子串 $S[i+1, i+l+1)$ 的哈希值。
$h(S[i+1, i + l + 1)) = (h(S[i, i+l) ) - S[i] p^{l-1} ) p + S[i+l] $ - $O(n)$ 预处理每个前缀的哈希值 $h_i$ 之后可以 $O(1)$ 地求出任意子串的哈希值。
$h(S[l,r]) = h_r - h_{l-1} p^{r-l+1} $
莫队
平方根分块（query sqrt decomposition）