From eba5d09835731c020924df6118ce186977bbe961 Mon Sep 17 00:00:00 2001
From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com>
Date: Thu, 19 Nov 2020 03:14:36 -0500
Subject: [PATCH] style: format markdown files with remark-lint

---
 docs/geometry/random-incremental.md |   5 +-
 docs/misc/rand-technique.md         | 150 ++++++++++++++++++------------------
 docs/misc/random.md                 |  30 ++++----
 3 files changed, 94 insertions(+), 91 deletions(-)

diff --git a/docs/geometry/random-incremental.md b/docs/geometry/random-incremental.md
index 692efdc7..958adf79 100644
--- a/docs/geometry/random-incremental.md
+++ b/docs/geometry/random-incremental.md
@@ -112,8 +112,7 @@ $$
 
  [「HNOI2012」射箭](https://www.luogu.com.cn/problem/P3222) 
 
- [CodeForces 442E](https://codeforces.com/problemset/problem/442/E)
-
+ [CodeForces 442E](https://codeforces.com/problemset/problem/442/E) 
 
 ## 参考资料与扩展阅读
 
@@ -123,4 +122,4 @@ $$
 
  <https://wenku.baidu.com/view/162699d63186bceb19e8bbe6.html> 
 
- <https://blog.csdn.net/u014609452/article/details/62039612>
\ No newline at end of file
+ <https://blog.csdn.net/u014609452/article/details/62039612> 
diff --git a/docs/misc/rand-technique.md b/docs/misc/rand-technique.md
index 7eb12ee1..de9d6ee8 100644
--- a/docs/misc/rand-technique.md
+++ b/docs/misc/rand-technique.md
@@ -2,7 +2,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
 ## 概述
 
-前置知识：[随机函数](../misc/random.md)和[概率初步](../math/expectation.md)
+前置知识： [随机函数](../misc/random.md) 和 [概率初步](../math/expectation.md) 
 
 本文将对 OI/ICPC 中的随机化相关技巧做一个简单的分类，并对每个分类予以介绍。本文也将介绍一些在 OI/ICPC 中很少使用，但与 OI/ICPC 在风格等方面较为贴近的方法，这些内容前将用 `(*)` 标注。
 
@@ -10,8 +10,8 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
  **记号和约定** ：
 
- -  $\mathrm{Pr}[A]$ 表示事件 $A$ 发生的概率。
- -  $\mathrm{E}[X]$ 表示随机变量 $X$ 的期望。
+-  $\mathrm{Pr}[A]$ 表示事件 $A$ 发生的概率。
+-  $\mathrm{E}[X]$ 表示随机变量 $X$ 的期望。
 
 ## 用随机集合覆盖目标元素
 
@@ -21,7 +21,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
 问题：给定一张 $n$ 个结点、 $m$ 条边的简单无向图，用 RGB 三种颜色给每个结点染色 满足任意一对邻居都不同色，或者报告无解。
 
-对每个点 $v$ ，从 $\{R,G,B\}$ 中等概率独立随机地选一种颜色 $C_v$ ，并钦定 $v$ **不** 被染成 $C_v$ 。最优解恰好符合这些限制的概率，显然是 $\big(\frac 23\big)^n$ 。
+对每个点 $v$ ，从 $\{R,G,B\}$ 中等概率独立随机地选一种颜色 $C_v$ ，并钦定 $v$  **不** 被染成 $C_v$ 。最优解恰好符合这些限制的概率，显然是 $\big(\frac 23\big)^n$ 。
 
 在这些限制下，对于一对邻居 $(u,v)$ ，“ $u,v$ 不同色”的要求等价于以下这条“推出”关系：
 
@@ -31,7 +31,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
 这样做，单次的正确率是 $\big(\frac 23\big)^n$ 。将算法重复运行 $-\big(\frac 32\big)^n\log \epsilon$ 次，只要有一次得到解就输出，这样即可保证 $1-\epsilon$ 的正确率。（详见后文中“自然常数的使用”和“抽奖问题”）
 
-### 例： [CodeChef SELEDGE](https://www.codechef.com/problems/SELEDGE)
+### 例： [CodeChef SELEDGE](https://www.codechef.com/problems/SELEDGE) 
 
 观察：如果选出的边中有三条边构成一条链，则删掉中间的那条一定不劣；如果选出的边中有若干条构成环，则删掉任何一条一定不劣。
 
@@ -49,16 +49,16 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
 在上述要求下，尝试建立费用流模型计算最优答案：
 
-- 建立二分图，白点在左侧并与 $S$ 相连，黑点在右侧并与 $T$ 相连。
-    - 对于白点 $v$ ，从 $S$ 向它连一条容量为 1 、费用为 $-A_v$ 的边，和一条容量为 $\infty$ 、费用为 0 的边。
-    - 对于黑点 $v$ ，从它向 $T$ 连一条容量为 1 、费用为 $-A_v$ 的边，和一条容量为 $\infty$ 、费用为 0 的边。
-- 对于原图中的边 $(u,v,B)$ 满足 $u$ 为白色、 $v$ 为黑色，连一条从 $u$ 到 $v$ 的边，容量为 1 ，费用为 $B$ 。
+-   建立二分图，白点在左侧并与 $S$ 相连，黑点在右侧并与 $T$ 相连。
+    - 对于白点 $v$ ，从 $S$ 向它连一条容量为 1、费用为 $-A_v$ 的边，和一条容量为 $\infty$ 、费用为 0 的边。
+    - 对于黑点 $v$ ，从它向 $T$ 连一条容量为 1、费用为 $-A_v$ 的边，和一条容量为 $\infty$ 、费用为 0 的边。
+- 对于原图中的边 $(u,v,B)$ 满足 $u$ 为白色、 $v$ 为黑色，连一条从 $u$ 到 $v$ 的边，容量为 1，费用为 $B$ 。
 - 在该图中限制流量不超过 $K$ ，则最小费用的相反数就是答案。
 
 用 SPFA 费用流求解的话，复杂度是 $O(K^2(n+m))$ ，证明：
 
 - 首先，显然 SPFA 的运行次数 $\leq K$ 。
-- 然后，在一次 SPFA 中，任何一个结点至多入队 $O(K)$ 次。这是因为：
+-   然后，在一次 SPFA 中，任何一个结点至多入队 $O(K)$ 次。这是因为：
     - 任意时刻有流量的边不会超过 $3K$ 条，否则就意味着在原图中选了超过 $K$ 条边。
     - 对于任何一条长为 $L$ 的增广路，其中至少有 $\dfrac L2-2$ 条边是某条有流量的边的反向边，因为正向边都是从图的左侧指向右侧，只有这些反向边才会从右侧指向左侧。
     - 综合以上两条，得到任意一条增广路的长度不超过 $6K+4$ 。
@@ -70,12 +70,12 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
 我们需要确定一个集合中的任意一个元素，为此我们随机选取元素，以期能够恰好命中这一集合。
 
-### 例： [Gym 101550I](https://codeforces.com/gym/101550/attachments)
+### 例： [Gym 101550I](https://codeforces.com/gym/101550/attachments) 
 
 整张图可以拆分为一个环加上四条从环伸出去的链。对于这四条链中的任何一条（记作 $C$ ），考虑在这条链上如何放置窃听器，容易通过贪心算法得到满足以下条件的方案：
 
 - 在拦截所有 $C$ 内部进行的通话的前提下，用的窃听器数量最少。
-- 在上一条的前提下，使得 $C$ 上的窃听器离环的最短距离尽可能小。
+-   在上一条的前提下，使得 $C$ 上的窃听器离环的最短距离尽可能小。
     - 作这一要求的目的是尽可能地拦截恰有一个端点在 $C$ 内部的通话。
 
 接着考虑链与环相接处的共计 4 条边，我们暴力枚举这些边上有没有放窃听器。显然，如果想要拦截跨越链和环的通话，在这 4 条边上放窃听器一定是最优的。现在，我们可以把通话线路分为以下几种：
@@ -107,15 +107,15 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
 综上，该算法的复杂度 $O(|S|\cdot -\dfrac n{|S|}\log\epsilon)=O(-n\log\epsilon)$ 。
 
-### 例： [CSES 1685 New Flight Routes](https://cses.fi/problemset/task/1685)
+### 例： [CSES 1685 New Flight Routes](https://cses.fi/problemset/task/1685) 
 
 先对原图进行强连通缩点。我们的目标显然是使每个汇点能到达每个源点。
 
 不难证明，我们一定只会从汇点到源点连边，因为任何其他的连边，都能对应上一条不弱于它的、从汇点到源点的连边。
 
-我们的一个核心操作是，取汇点 $t$ 和源点 $s$ （它们不必在同一个弱连通分量里），连边 $t\to s$ 以 **使得 $s$ 和 $t$ 都不再是汇点或源点** （记作目标 I ）。理想情况下这种操作每次能减少一个汇点和一个源点，那我们不断操作直到只剩一个汇点或只剩一个源点 ，而这样的情形就很平凡了。由此，我们猜测答案是源点个数与汇点个数的较大值。
+我们的一个核心操作是，取汇点 $t$ 和源点 $s$ （它们不必在同一个弱连通分量里），连边 $t\to s$ 以 **使得 $s$ 和 $t$ 都不再是汇点或源点** （记作目标 I）。理想情况下这种操作每次能减少一个汇点和一个源点，那我们不断操作直到只剩一个汇点或只剩一个源点，而这样的情形就很平凡了。由此，我们猜测答案是源点个数与汇点个数的较大值。
 
-不难发现，上述操作能够达到目标 I 的充要条件是： $t$ 拥有 $s$ 以外的前驱、且 $s$ 拥有 $t$ 以外的后继。可以证明（等会会给出证明），对于任意一张有着至少一个源点、至少一个汇点的DAG，都存在这样的 $(s,t)$ ；但存在性的结论不能帮助我们得到算法，还需做其他分析。
+不难发现，上述操作能够达到目标 I 的充要条件是： $t$ 拥有 $s$ 以外的前驱、且 $s$ 拥有 $t$ 以外的后继。可以证明（等会会给出证明），对于任意一张有着至少一个源点、至少一个汇点的 DAG，都存在这样的 $(s,t)$ ；但存在性的结论不能帮助我们得到算法，还需做其他分析。
 
 - 有了这个充要条件还难以直接得到算法，主要的原因是连边 $t\to s$ 后可能影响其他 $(s',t')$ 二元组的合法性，这个比较难处理。
 
@@ -130,25 +130,28 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
 - 注意到这个结论严格强于先前给出的存在性结论。
 
-推论：等概率独立随机地连续选取 $\dfrac {\min(n,m)}2$ 对不含公共元素的 $(s,t)$ ，并对它们**依次**操作（即连边 $t\to s$ ），则这些操作全部满足目标 I 的概率 $\geq \dfrac 14$ 。
+推论：等概率独立随机地连续选取 $\dfrac {\min(n,m)}2$ 对不含公共元素的 $(s,t)$ ，并对它们 **依次** 操作（即连边 $t\to s$ ），则这些操作全部满足目标 I 的概率 $\geq \dfrac 14$ 。
 
 - 理由： $\dfrac {(n-1)(m-1)}{nm}\cdot\dfrac{(n-2)(m-2)}{(n-1)(m-1)}\cdots\dfrac{(n-k)(m-k)}{(n-k+1)(m-k+1)}=\dfrac{(n-k)(m-k)}{nm}\geq \dfrac 14$ 
 
-而连续选完 $k$ 对 $(s,t)$ 后判断它们是否全部满足目标 I 很简单，只要再跑一遍强连通缩点，判断一下 $n,m$ 是否都减小了 $k$ 即可。注意到若每次减少 $k=\dfrac{\min(n,m)}2$ ，则 $min(n,m)$ 必在 $O(\log(n+m))$ 轮内变成 1 ，也就转化到了平凡的情况。
+而连续选完 $k$ 对 $(s,t)$ 后判断它们是否全部满足目标 I 很简单，只要再跑一遍强连通缩点，判断一下 $n,m$ 是否都减小了 $k$ 即可。注意到若每次减少 $k=\dfrac{\min(n,m)}2$ ，则 $min(n,m)$ 必在 $O(\log(n+m))$ 轮内变成 1，也就转化到了平凡的情况。
 
 ???+ note "算法伪代码"
     ```
-	while(n>1 and m>1):
-		randomly choose k=min(n,m)/2 pairs (s,t)
-		add edge t->s for all these pairs
-		if new_n>n-k or new_m>m-k:
-			roll_back()
-	solve_trivial()
+    
+    ```
+
+    while(n>1 and m>1):
+    	randomly choose k=min(n,m)/2 pairs (s,t)
+    	add edge t->s for all these pairs
+    	if new_n>n-k or new_m>m-k:
+    		roll_back()
+    solve_trivial()
     ```
 
 复杂度 $O((|V|+|E|) \log |V|)$ 。
 
-**回顾** ：我们需要确定任意一对能够实现目标 I 的二元组 $(s,t)$ ，为此我们随机选择 $(s,t)$ 。
+ **回顾** ：我们需要确定任意一对能够实现目标 I 的二元组 $(s,t)$ ，为此我们随机选择 $(s,t)$ 。
 
 ## 用随机化获得随机数据的性质
 
@@ -162,28 +165,28 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
 不难想到折半搜索。把点集均匀分成左右两半 $V_L,V_R$ （大小都为 $\dfrac n2$ ），计算数组 $f_{L,k}$ 表示点集 $L\subseteq V_L$ 中的所有 $\geq k$ 元团的最大权值和。接着我们枚举右半边的每个团 $C_R$ ，算出左半边有哪些点与 $C_R$ 中的所有点相连（这个点集记作 $N_L$ ），并用 $f_{N_L,\frac 23 n-|C_R|}+\textit{value}(C_R)$ 更新答案。
 
-- 注意到可以 $O(1)$ 转移每一个 $f_{L,k}$ 。具体地说，取 $d$ 为 $L$ 中的任意一个元素，然后分类讨论：
+-   注意到可以 $O(1)$ 转移每一个 $f_{L,k}$ 。具体地说，取 $d$ 为 $L$ 中的任意一个元素，然后分类讨论：
     - 假设最优解中 $d$ 不在团中，则从 $f_{L\setminus \{d\},k}$ 转移而来。
     - 假设最优解中 $d$ 在团中，则从 $f_{L\cap N(d),k}+\textit{value}(d)$ 转移而来，其中 $N(d)$ 表示 $d$ 的邻居集合。
     - 别忘了还要用 $f_{L,k+1}$ 来更新 $f_{L,k}$ 。
 
 这个解法会超时。尝试优化：
 
-- 平分点集时均匀随机地划分。这样的话，最优解的点集 $C_{res}$ 以可观的概率也被恰好平分（即 $|C_{res}\cap V_L|=|C_{res}\cap V_R|$ ）。
+-   平分点集时均匀随机地划分。这样的话，最优解的点集 $C_{res}$ 以可观的概率也被恰好平分（即 $|C_{res}\cap V_L|=|C_{res}\cap V_R|$ ）。
     - 当然， $|C_{res}|$ 可能是奇数。简单起见，这里假设它是偶数；奇数的情况对解法没有本质改变。
     - 实验发现，随机尝试约 20 次就能以很大概率有至少一次满足该性质。也就是说，如果我们的算法依赖于“ $C_{res}$ 被平分”这一性质，则将算法重复执行 20 次取最优，同样也能保证以很大概率得到正确答案。
-- 有了这一性质，我们就可以直接钦定左侧团 $L$ 、右侧团 $C_R$ 的大小都 $\geq \dfrac n3$ 。这会对复杂度带来两处改进：
-    - $f$ 可以省掉记录大小的维度。
+-   有了这一性质，我们就可以直接钦定左侧团 $L$ 、右侧团 $C_R$ 的大小都 $\geq \dfrac n3$ 。这会对复杂度带来两处改进：
+    -  $f$ 可以省掉记录大小的维度。
     - 因为只需考虑大小 $\geq \dfrac n3$ 的团，所以需要考虑的左侧团 $L$ 和 右侧团 $C_R$ 的数量也大大减少至约 $1.8\cdot 10^6$ 。
-- 现在的瓶颈变成了求单侧的某一子集的权值和，因为这需要 $O(2^{|V_L|}+2^{|V_R|})$ 的预处理。
+-   现在的瓶颈变成了求单侧的某一子集的权值和，因为这需要 $O(2^{|V_L|}+2^{|V_R|})$ 的预处理。
     - 解决方案：在 $V_L,V_R$ 内部再次折半；当查询一个子集的权值和时，将这个子集分成左右两半查询，再把答案相加。
 - 这样即可通过本题。
 
-**回顾** ：一个随机的集合有着“在划分出的两半的数量差距不会太悬殊”这一性质，而我们通过随机划分获取了这个性质。
+ **回顾** ：一个随机的集合有着“在划分出的两半的数量差距不会太悬殊”这一性质，而我们通过随机划分获取了这个性质。
 
 ## 随机化用于哈希
 
-### 例： [UOJ #207 共价大爷游长沙](https://uoj.ac/problem/207)
+### 例： [UOJ #207 共价大爷游长沙](https://uoj.ac/problem/207) 
 
 对图中的每条边 $e$ ，我们定义集合 $S_e$ 表示经过该边的关键路径（即题中的 $(a,b)$ ）集合。考虑对每条边动态维护集合 $S_e$ 的哈希值，这样就能轻松判定 $S_e$ 是否等于全集（即 $e$ 是否是“必经之路”）。
 
@@ -217,7 +220,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 - 假设上述做法求得了不同于 $F$ （且显然也不长于 $F$ ）的 $l$ 阶递推式 $F'$ 。
 - 因为矩阵序列不服从 $F'$ ，所以一定存在矩阵中的某个位置 $(i,j)$ ，满足该位置对应的数列 $S_{i,j}$ 在某个 $N$ 处不服从 $F'$ 。也就是说 $S(N)_{i,j}-F'_1S(N-1)_{i,j}-\cdots-F'_lS(N-l)_{i,j}\not\equiv 0(\bmod P)$ 。
 - 假设 $(i,j)$ 是唯一的不服从的位置，则一定有 $T_{i,j}:=x_{i,j}\cdot(S(N)_{i,j}-F'_1S(N-1)_{i,j}-\cdots-F'_lS(N-l)_{i,j})\bmod P=0$ 。显然这仅当 $x_{i,j}=0$ 时才成立，概率 $P^{-1}$ 。
-- 如果有多个不服从的位置呢？
+-   如果有多个不服从的位置呢？
     - 对每个这样的位置 $(i,j)$ ，易证 $T_{i,j}$ 服从 $R:=\{0,1,\cdots,P-1\}$ 上的均匀分布。
     - 若干个互相独立的、服从 $R$ 上的均匀分布的随机变量，它们在模意义下的和，依然服从 $R$ 上的均匀分布。自证不难。
     - 从而这种情况下的错误率也是 $P^{-1}$ 。
@@ -239,16 +242,16 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
     推论：若 $x_1,\cdots,x_k$ 都在 $S$ 中等概率独立随机选取，则 $\mathrm{Pr}\big[f(x_1,\cdots,x_k)=0\big]\leq \dfrac d{|S|}$ 。
 
-记 $F$ 为模 $Q$ 的剩余系所对应的数域，则对于一个 $L\leq n_1+n_2$ ，$\sum\limits_i f_{0,i,L}$ 和 $\sum\limits_i f_{1,i,L}$ 就分别对应着一个 $F$ 上关于变元 $x_{*,*}$ 的 $L$ 次多元多项式，不妨将这两个多项式记为 $P_0,P_1$ 。
+记 $F$ 为模 $Q$ 的剩余系所对应的数域，则对于一个 $L\leq n_1+n_2$ ， $\sum\limits_i f_{0,i,L}$ 和 $\sum\limits_i f_{1,i,L}$ 就分别对应着一个 $F$ 上关于变元 $x_{*,*}$ 的 $L$ 次多元多项式，不妨将这两个多项式记为 $P_0,P_1$ 。
 
 假如两个不同的字符串多重集的哈希值相同，则有两种可能：
 
-1. $P_0\equiv P_1(\bmod Q)$ ，即 $P_0,P_1$ 的每一项系数在模 $Q$ 意义下都对应相等。
-2. $P_0\not\equiv P_1(\bmod Q), P_0(x_{*,*})\equiv P_1(x_{*,*})(\bmod Q)$ ，即 $P_0,P_1$ 虽然不恒等，但我们选取的这一组 $x_{*,*}$ 恰好使得它们在此处的点值相等。
+1.  $P_0\equiv P_1(\bmod Q)$ ，即 $P_0,P_1$ 的每一项系数在模 $Q$ 意义下都对应相等。
+2.  $P_0\not\equiv P_1(\bmod Q), P_0(x_{*,*})\equiv P_1(x_{*,*})(\bmod Q)$ ，即 $P_0,P_1$ 虽然不恒等，但我们选取的这一组 $x_{*,*}$ 恰好使得它们在此处的点值相等。
 
 分析前者发生的概率：
 
-- 观察：对于任意的 $A\neq B; A,B\leq N$ 和随机选取的质数 $Q\leq Q_{max}$ ，$\mathrm{Pr}[A\equiv B(\bmod Q)]=O\big(\dfrac{\log N \log Q_{max}}{Q_{max}}\big)$
+-   观察：对于任意的 $A\neq B; A,B\leq N$ 和随机选取的质数 $Q\leq Q_{max}$ ， $\mathrm{Pr}[A\equiv B(\bmod Q)]=O\big(\dfrac{\log N \log Q_{max}}{Q_{max}}\big)$ 
     - 理由：使 $A\equiv B$ 成立的 $Q$ 一定满足 $Q|(A-B)$ ，这样的 $Q$ 至多有 $d(A-B)\leq log_2 N$ 个；而由质数定理， $Q_{max}$ 以内不同的质数又有 $\Theta(\dfrac {Q_{max}}{\log Q_{max}})$ 个。将两者相除即可。
 - 在上述观察中取 $A,B$ 满足 $A\neq B$ 为某一特定项在 $P_0,P_1$ 中的系数（也就等于该项对应的串在 $G_0,G_1$ 中的出现次数），则易见 $A,B\leq (m_1+m_2)^{L}$ ，得到 $\mathrm{Pr}[A\equiv B(\bmod Q)]=O\big(\dfrac{L\log (m_1+m_2) \log Q_{max}}{Q_{max}}\big)$ ，所以取 $Q_{max}\approx 10^{12}$ 就绰绰有余。如果机器无法支持这么大的整数运算，可以用双哈希代替。
 
@@ -256,11 +259,11 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
 - 直接套用 Schwartz-Zippel 引理，得到该概率 $\leq \dfrac LQ$ 。
 
-注意到我们需要对每个 $L$ 都能保证正确性，所以要想保证严谨的话还需用 Union Bound （见后文）说明一下。
+注意到我们需要对每个 $L$ 都能保证正确性，所以要想保证严谨的话还需用 Union Bound（见后文）说明一下。
 
 实践上我们不必随机选取模数，因为——比如说——用自己的生日做模数的话，实际上已经相当于随机数了。
 
-### 例：(\*)子矩阵不同元素个数
+### 例：(\*）子矩阵不同元素个数
 
 ???+ note "问题"
     给定 $n\times m$ 的矩阵， $q$ 次询问一个连续子矩阵中不同元素的个数，要求在线算法。
@@ -279,7 +282,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
     考虑采用某个哈希函数，将矩阵中每个元素都均匀、独立地随机映射到 $[0,1]$ 中的实数上去，且相等的元素会映射到相等的实数。这样的话，一个子矩阵中的所有元素对应的那些实数，在去重后就恰好是先前的集合 $\{X_1,\cdots,X_k\}$ 的一个实例，其中 $k$ 等于子矩阵中不同元素的个数。
 
     于是我们得到了算法：
-    
+
     1. 给矩阵中元素赋 $[0,1]$ 中的哈希值。为保证随机性，哈希函数可以直接用 `map` 和随机数生成器实现，即每遇到一个新的未出现过的值就给它随机一个哈希值。
     2. 回答询问时设法求出子矩阵中哈希值的最小值 $M$ ，并输出 $\dfrac 1M-1$ 。
 
@@ -299,22 +302,23 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
 随机化的其他作用还包括：
 
--  防止被造数据者用针对性数据卡掉。例如在搜索时随机打乱邻居的顺序。
--  保证算法过程中进行的“操作”具有（某种意义上的）均匀性。例如 [模拟退火](../misc/simulated-annealing.md) 算法。
+- 防止被造数据者用针对性数据卡掉。例如在搜索时随机打乱邻居的顺序。
+- 保证算法过程中进行的“操作”具有（某种意义上的）均匀性。例如 [模拟退火](../misc/simulated-annealing.md) 算法。
 
 在这些场景下，随机化常常（但并不总是）与乱搞、骗分等做法挂钩。
 
-### 例：[「TJOI2015」线性代数](https://loj.ac/problem/2100) 
+### 例： [「TJOI2015」线性代数](https://loj.ac/problem/2100) 
 
 本题的标准算法是网络流，但这里我们采取这样的乱搞做法：
 
--  每次随机一个位置，把这个位置取反，判断大小并更新答案。
+- 每次随机一个位置，把这个位置取反，判断大小并更新答案。
 
 ??? note "代码"
     ```cpp
     #include <algorithm>
     #include <cstdlib>
     #include <iostream>
+    ```
 
     int n;
 
@@ -349,7 +353,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
     }
     ```
 
-### 例：(\*)随机堆
+### 例：(\*）随机堆
 
 可并堆最常用的写法应该是左偏树了，通过维护树高让树左偏来保证合并的复杂度。然而维护树高有点麻烦，我们希望尽量避开。
 
@@ -362,6 +366,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
       long long val;
     } nd[100010];
     int root[100010];
+    ```
 
     int merge(int u, int v) {
       if (!(u && v)) return u | v;
@@ -376,7 +381,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 随机堆对堆的形态没有任何硬性或软性的要求，合并操作的期望复杂度对任何两个堆（作为 `merge` 函数的参数）都成立。下证。
 
 ???+ note "期望复杂度的证明"
-    将证，对于任意的堆 $A$ ，从根节点开始每次随机选左或者右走下去（直到无路可走），路径长度（即路径上的结点数）的期望值 $h(A)\leq\log_2 (|A|+1)$。
+    将证，对于任意的堆 $A$ ，从根节点开始每次随机选左或者右走下去（直到无路可走），路径长度（即路径上的结点数）的期望值 $h(A)\leq\log_2 (|A|+1)$ 。
 
     - 注意到在前述过程中合并堆 $A,B$ 的期望复杂度是 $O(h(A)+h(B))$ 的，所以上述结论可以保证随机堆的期望复杂度。
 
@@ -395,7 +400,6 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
     证毕。
 
-
 ## 与随机性有关的证明技巧
 
 以下列举几个比较有用的技巧。
@@ -410,32 +414,32 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ
 
 #### 工具
 
-**Union Bound** ：记 $A_{1\cdots m}$ 为坏事件，则
+ **Union Bound** ：记 $A_{1\cdots m}$ 为坏事件，则
 
 $$
 \mathrm{Pr}\Big[\bigcup\limits_{i=1}^m A_i \Big]\leq \sum\limits_{i=1}^m \mathrm{Pr}[A_i]
 $$
 
--  即：坏事件中至少一者发生的概率，不超过每一个的发生概率之和。
--  证明：回到概率的定义，把事件看成单位事件的集合，发现这个结论是显然的。
--  这一结论还可以稍作加强：
-    -  坏事件中至少一者发生的概率， **不小于** 每一个的发生概率之和，减掉每两个同时发生的概率之和。
-    -  坏事件中至少一者发生的概率， **不超过** 每一个的发生概率之和，减掉每两个同时发生的概率之和，加上每三个同时发生的概率之和。
-    -  ……
-    -  随着层数越来越多，交替出现的上界和下界也越来越紧。这一系列结论形式上类似容斥原理，证明过程也和容斥类似，这里略去。
+- 即：坏事件中至少一者发生的概率，不超过每一个的发生概率之和。
+- 证明：回到概率的定义，把事件看成单位事件的集合，发现这个结论是显然的。
+-   这一结论还可以稍作加强：
+    - 坏事件中至少一者发生的概率， **不小于** 每一个的发生概率之和，减掉每两个同时发生的概率之和。
+    - 坏事件中至少一者发生的概率， **不超过** 每一个的发生概率之和，减掉每两个同时发生的概率之和，加上每三个同时发生的概率之和。
+    - ……
+    - 随着层数越来越多，交替出现的上界和下界也越来越紧。这一系列结论形式上类似容斥原理，证明过程也和容斥类似，这里略去。
 
-**自然常数的使用** ： $\Big(1-\dfrac 1n\Big)^n\leq \dfrac 1e,\forall n\geq1$
+ **自然常数的使用** ： $\Big(1-\dfrac 1n\Big)^n\leq \dfrac 1e,\forall n\geq1$ 
 
--  左式关于 $n\geq 1$ 单调递增且在 $+\infty$ 处的极限是 $\dfrac 1e$ ，因此有这个结论。
--  这告诉我们，如果 $n$ 个互相独立的坏事件，每个的发生概率为 $1-\dfrac 1n$ ，则它们全部发生的概率至多为 $\dfrac 1e$ 。
+- 左式关于 $n\geq 1$ 单调递增且在 $+\infty$ 处的极限是 $\dfrac 1e$ ，因此有这个结论。
+- 这告诉我们，如果 $n$ 个互相独立的坏事件，每个的发生概率为 $1-\dfrac 1n$ ，则它们全部发生的概率至多为 $\dfrac 1e$ 。
 
-**(\*) Hoeffding** 不等式：若 $X_{1\cdots n}$  为互相独立的实随机变量且 $X_i\in [a_i,b_i]$ ，记随机变量 $X:=\sum\limits_{i=1}^n X_i$ ，则
+ **(\*) Hoeffding** 不等式：若 $X_{1\cdots n}$ 为互相独立的实随机变量且 $X_i\in [a_i,b_i]$ ，记随机变量 $X:=\sum\limits_{i=1}^n X_i$ ，则
 
 $$
 \mathrm{Pr}\Big[\big|X-\mathrm{E}[X]\big|\geq t\Big]\leq2\exp {-\dfrac {t^2}{\sum\limits_{i=1}^n (b_i-a_i)^2}}
 $$
 
--  这一不等式限制了随机变量偏离其期望值的程度。从经验上讲，如果 $\mathrm{E}[X]$ 不太接近 $a_1+\cdots+a_n$ ，则该不等式给出的界往往相对比较紧；如果非常接近的话（例如在 [UOJ #72 全新做法](https://matthew99.blog.uoj.ac/blog/5511) 中），给出的界则往往很松，此时更好的选择是使用 (\*)[Chernoff Bound](https://en.wikipedia.org/wiki/Chernoff_bound) ，它和 Hoeffding 不等式同属于 (\*)[Concentration Inequality](https://en.wikipedia.org/wiki/Concentration_inequality) 。
+- 这一不等式限制了随机变量偏离其期望值的程度。从经验上讲，如果 $\mathrm{E}[X]$ 不太接近 $a_1+\cdots+a_n$ ，则该不等式给出的界往往相对比较紧；如果非常接近的话（例如在 [UOJ #72 全新做法](https://matthew99.blog.uoj.ac/blog/5511) 中），给出的界则往往很松，此时更好的选择是使用 (\*) [Chernoff Bound](https://en.wikipedia.org/wiki/Chernoff_bound) ，它和 Hoeffding 不等式同属于 (\*) [Concentration Inequality](https://en.wikipedia.org/wiki/Concentration_inequality) 。
 
 #### 例子
 
@@ -445,9 +449,9 @@ $$
 与该问题类似的模型经常出现在随机算法的复杂度分析中。
 
 ??? note "解答"
-    假如只有一个奖球 ，则抽取 $M:=-n\log\epsilon$ 次即可保证，因为 $M$ 次全不中的概率 $\Big(1-\dfrac 1n\Big)^{n\cdot (-\log\epsilon)}\leq e^{\log\epsilon}=\epsilon$ 。
+    假如只有一个奖球，则抽取 $M:=-n\log\epsilon$ 次即可保证，因为 $M$ 次全不中的概率 $\Big(1-\dfrac 1n\Big)^{n\cdot (-\log\epsilon)}\leq e^{\log\epsilon}=\epsilon$ 。
     
-    现在有 $k>1$ 个奖球，那么根据 Union Bound ，我们只需保证每个奖球被漏掉的概率都不超过 $\dfrac \epsilon k$ 即可。于是答案是 $-n\log\dfrac \epsilon k$ 。
+    现在有 $k>1$ 个奖球，那么根据 Union Bound，我们只需保证每个奖球被漏掉的概率都不超过 $\dfrac \epsilon k$ 即可。于是答案是 $-n\log\dfrac \epsilon k$ 。
 
 ???+ note "例：(\*)随机选取一半元素"
     给出一个算法，从 $n$ 个元素中等概率随机选取一个大小为 $\dfrac n2$ 的子集，保证 $n$ 是偶数。你能使用的唯一的随机源是一枚均匀硬币，同时请你尽量减少抛硬币的次数（不要求最少）。
@@ -478,7 +482,7 @@ $$
     尝试分析第二步所需的操作次数：
 
     - 记 01 随机变量 $X_i$ 表示 $i$ 是否被选入初始的子集，令 $X:=X_1+\cdots+X_n$ 表示子集大小，则第二步所需的操作次数等于 $\big|X-\mathrm{E}[X]\big|$ 。在 Hoeffding 不等式中取 $t=c\cdot\sqrt n$ （其中 $c$ 为任意常数），得到 $\mathrm{Pr}\Big[\big|X-\mathrm{E}[X]\big|\geq t\Big]\leq 2e^{-c^2}$ 。也就是说，我们可以通过允许 $\Theta(\sqrt n)$ 级别的偏移，来得到任意小的常数级别的失败概率。（注意到这并不一定说明偏移量的期望值就是 $\Theta(\sqrt n)$ ）
-    
+
     至此我们已经基本能够确信，第二步的操作次数应该不是瓶颈，该算法的期望抛硬币次数应该是 $n+o(n)$ 。
 
     ??? mdui-shadow-6 "闲得无聊想算精确的式子"
@@ -503,7 +507,7 @@ $$
 这个结论看起来再自然不过，但严格证明却并不那么容易。
 
 ??? note "大致思路"
-    我们假想这两张图分别使用了一个 01 随机数生成器来获知每条边存在与否，其中 $G_1$ 的生成器 $T_1$ 每次以 $p$ 的概率输出 1 ，$G_2$ 的生成器 $T_2$ 每次以 $q$ 的概率输出 1 。这样，要构造一张图，就只需把对应的生成器运行 $\dfrac {n(n-1)}2$ 遍即可。
+    我们假想这两张图分别使用了一个 01 随机数生成器来获知每条边存在与否，其中 $G_1$ 的生成器 $T_1$ 每次以 $p$ 的概率输出 1， $G_2$ 的生成器 $T_2$ 每次以 $q$ 的概率输出 1。这样，要构造一张图，就只需把对应的生成器运行 $\dfrac {n(n-1)}2$ 遍即可。
 
     现在我们把两个生成器合二为一。考虑随机数生成器 $T$ ，每次以 $q$ 的概率输出 0 ，以 $p-q$ 的概率输出 1 ，以 $1-p$ 的概率输出 2 。如果我们将这个 $T$ 运行 $\dfrac {n(n-1)}2$ 遍，就能同时构造出 $G_1$ 和 $G_2$ 。具体地说，如果输出是 0 ，则认为 $G_1$ 和 $G_2$ 中都没有当前考虑的边；如果输出是 1 ，则认为只有 $G_1$ 中有当前考虑的边；如果输出是 2 ，则认为 $G_1$ 和 $G_2$ 中都有当前考虑的边。
 
@@ -511,11 +515,11 @@ $$
 
 这一段证明中用到的思想被称为“耦合”，可以从字面意思来理解这种思想。本例中它体现为把两个本来独立的随机过程合二为一。
 
-#### 应用： [NERC 2019 Problem G: Game Relics](https://codeforces.com/contest/1267/problem/G)
+#### 应用： [NERC 2019 Problem G: Game Relics](https://codeforces.com/contest/1267/problem/G) 
 
 观察：如果选择抽物品，就一定会一直抽直到获得新物品为止。
 
--  理由：如果抽一次没有获得新物品，则新的局面和抽物品之前的局面一模一样，所以如果旧局面的最优行动是“抽一发”，则新局面的最优行动一定也是“再抽一发”。
+- 理由：如果抽一次没有获得新物品，则新的局面和抽物品之前的局面一模一样，所以如果旧局面的最优行动是“抽一发”，则新局面的最优行动一定也是“再抽一发”。
 
 我们可以计算出 $f_k$ 表示：如果当前已经拥有 $k$ 个不同物品，则期望要花多少钱才能抽到新物品。根据刚才的观察，我们可以直接把 $f_k$ 当作一个固定的代价，即转化为“每次花 $f_k$ 块钱随机获得一个新物品”。
 
@@ -540,9 +544,9 @@ $$
     -  随机过程 $A$ ：先买物品 $x$ ，然后不断抽直到得到所有物品
     -  ……一定不优于……
     -  随机过程 $B$ ：不断抽直到得到 $x$ 以外的所有物品，然后如果还没有 $x$ 则买下来
-    
+
     考虑让随机过程 $A$ 和随机过程 $B$ 使用同一个随机数生成器。即， $A$ 的第一次抽取和 $B$ 的第一次抽取会抽到同一个元素，第二次、第三次……也是一样。
-    
+
     显然，此时 $A$ 和 $B$ 抽取的次数必定相等。对于一个被 $A$ 抽到的物品 $y\neq x$ ，观察到：
 
     -  $A$ 中抽到 $y$ 时已经持有的物品数，一定大于等于 $B$ 中抽到 $y$ 时已经持有的物品数。
@@ -559,16 +563,16 @@ $$
 
 观察：在某一时刻，我们应当选择买，当且仅当下一次抽取的代价（由已经抽到的物品数确定）大于剩余物品的平均价格（等于的话则任意）。
 
--  可以证明，随着时间的推移，抽取代价的增速一定不低于剩余物品均价的增速。这说明从抽到买的“临界点”只有一个，进一步验证了先前结论。
+- 可以证明，随着时间的推移，抽取代价的增速一定不低于剩余物品均价的增速。这说明从抽到买的“临界点”只有一个，进一步验证了先前结论。
 
-最后，我们枚举所有可能的局面（即已经拥有的元素集合），算出这种局面出现的概率（已有元素的排列方案数除以总方案数），乘上当前局面最优决策的代价（由拥有元素个数和剩余物品总价确定），再加起来即可。这个过程可以用背包式的DP优化，即可通过本题。
+最后，我们枚举所有可能的局面（即已经拥有的元素集合），算出这种局面出现的概率（已有元素的排列方案数除以总方案数），乘上当前局面最优决策的代价（由拥有元素个数和剩余物品总价确定），再加起来即可。这个过程可以用背包式的 DP 优化，即可通过本题。
 
-**回顾** ：可以看到，耦合的技巧在本题中使用了两次。第一次是在证明过程中，令两个随机过程使用同一个随机源；第二次是把购买转化成随机购买（即引入随机源），从而使得购买和抽取这两种操作实质上“耦合”为同一种操作（即令抽取和购买操作共享一个随机源）。
+ **回顾** ：可以看到，耦合的技巧在本题中使用了两次。第一次是在证明过程中，令两个随机过程使用同一个随机源；第二次是把购买转化成随机购买（即引入随机源），从而使得购买和抽取这两种操作实质上“耦合”为同一种操作（即令抽取和购买操作共享一个随机源）。
 
 ## 参考资料
 
-[^ref1]:  [Anna Gambin and Adam Malinowski, Randomized Meldable Priority Queues](https://www.researchgate.net/publication/2801527_Randomized_Meldable_Priority_Queues)
+[^ref1]:  [Anna Gambin and Adam Malinowski, Randomized Meldable Priority Queues](https://www.researchgate.net/publication/2801527_Randomized_Meldable_Priority_Queues) 
 
-[^ref2]:  [UOJ NOI Round #4 Day2 题解](https://peehs-moorhsum.blog.uoj.ac/blog/6375)
+[^ref2]:  [UOJ NOI Round #4 Day2 题解](https://peehs-moorhsum.blog.uoj.ac/blog/6375) 
 
-[^ref3]:  [PANIC - Editorial](https://discuss.codechef.com/t/panic-editorial/80145)
\ No newline at end of file
+[^ref3]:  [PANIC - Editorial](https://discuss.codechef.com/t/panic-editorial/80145) 
diff --git a/docs/misc/random.md b/docs/misc/random.md
index bf9c8580..977b38cf 100644
--- a/docs/misc/random.md
+++ b/docs/misc/random.md
@@ -10,12 +10,12 @@
 
 然而在绝大部分情况下，我们都不需要如此强的随机性，而只需要所生成的数列在统计学上具有随机数列的种种特征（比如均匀分布、互相独立等等）。这样的数列即称为 **伪随机数** 序列。
 
-随机数与伪随机数在实际生活和算法中的应用举例:
+随机数与伪随机数在实际生活和算法中的应用举例：
 
--  抽样调查时往往只需使用伪随机数。这是因为我们本就只关心统计特征。
--  网络安全中往往要用到（比刚刚提到的伪随机数）更强的随机数。这是因为攻击者可能会利用可预测性做文章。
--  OI/ICPC 中用到的随机算法，基本都只需要伪随机数。这是因为，这些算法往往是 通过引入随机数 来把概率引入复杂度分析，从而降低复杂度。这本质上依然只利用了随机数的统计特征。
--  某些随机算法（例如 [Moser 算法](https://en.wikipedia.org/wiki/Algorithmic_Lov%C3%A1sz_local_lemma) ）用到了随机数的熵相关的性质，因此必须使用真正的随机数。
+- 抽样调查时往往只需使用伪随机数。这是因为我们本就只关心统计特征。
+- 网络安全中往往要用到（比刚刚提到的伪随机数）更强的随机数。这是因为攻击者可能会利用可预测性做文章。
+- OI/ICPC 中用到的随机算法，基本都只需要伪随机数。这是因为，这些算法往往是 通过引入随机数 来把概率引入复杂度分析，从而降低复杂度。这本质上依然只利用了随机数的统计特征。
+- 某些随机算法（例如 [Moser 算法](https://en.wikipedia.org/wiki/Algorithmic_Lov%C3%A1sz_local_lemma) ）用到了随机数的熵相关的性质，因此必须使用真正的随机数。
 
 ## 实现
 
@@ -36,9 +36,9 @@
 
 关于 `rand()` 和 `rand()%n` 的随机性：
 
--  C/C++ 标准并未关于 `rand()` 所生成随机数的任何方面的质量做任何规定。
--  GCC 编译器对 `rand()` 所采用的实现方式，保证了分布的均匀性等基本性质，但具有 低位周期长度短 等明显缺陷。（例如在笔者的机器上， `rand()%2` 所生成的序列的周期长约 2000000 ）
--  即使假设 `rand()` 是均匀随机的，`rand()%n` 也不能保证均匀性，因为 `[0,n)` 中的每个数在 `[0,RAND_MAX]` 中的出现次数可能不相同。
+- C/C++ 标准并未关于 `rand()` 所生成随机数的任何方面的质量做任何规定。
+- GCC 编译器对 `rand()` 所采用的实现方式，保证了分布的均匀性等基本性质，但具有 低位周期长度短 等明显缺陷。（例如在笔者的机器上， `rand()%2` 所生成的序列的周期长约 2000000）
+- 即使假设 `rand()` 是均匀随机的， `rand()%n` 也不能保证均匀性，因为 `[0,n)` 中的每个数在 `[0,RAND_MAX]` 中的出现次数可能不相同。
 
 ### mt19937
 
@@ -50,7 +50,7 @@
 
  `mt19937` 重载了 `operator ()` ，需要生成随机数时调用 `myrand()` 即可返回一个随机数。
 
- 另一个类似的生成器是 `mt19937_64` ，使用方式同 `mt19937` ，但随机数范围扩大到了 `unsigned long long` 类型的取值范围。
+另一个类似的生成器是 `mt19937_64` ，使用方式同 `mt19937` ，但随机数范围扩大到了 `unsigned long long` 类型的取值范围。
 
 #### 示例
 
@@ -78,9 +78,9 @@ int main() {
 
 关于 `random_shuffle` 的随机性：
 
--  C++ 标准中要求 `random_shuffle` 在所有可能的排列中 **等概率** 随机选取，但 GCC[^note1] 编译器 **并未** 严格执行。
--  GCC 中 `random_shuffle` 随机性上的缺陷的原因之一，是因为它使用了 `rand()%n` 这样的写法。如先前所述，这样生成的不是均匀随机的整数。
--  原因之二，是因为 `rand()` 的值域有限。如果所传入的区间长度超过 `RAND_MAX` ，将存在某些排列 **不可能** 被产生[^ref1]。
+- C++ 标准中要求 `random_shuffle` 在所有可能的排列中 **等概率** 随机选取，但 GCC[^note1]编译器 **并未** 严格执行。
+- GCC 中 `random_shuffle` 随机性上的缺陷的原因之一，是因为它使用了 `rand()%n` 这样的写法。如先前所述，这样生成的不是均匀随机的整数。
+- 原因之二，是因为 `rand()` 的值域有限。如果所传入的区间长度超过 `RAND_MAX` ，将存在某些排列 **不可能** 被产生[^ref1]。
 
 !!! warning
      `random_shuffle` 已于 C++14 标准中被弃用，于 C++17 标准中被移除。
@@ -91,7 +91,7 @@ int main() {
 
 区别在于必须使用自定义的随机数生成器： `std::shuffle(first, last, myrand)` 。
 
-GCC[^note1] 实现的 `shuffle` 符合 C++ 标准的要求，即在所有可能的排列中等概率随机选取。
+GCC[^note1]实现的 `shuffle` 符合 C++ 标准的要求，即在所有可能的排列中等概率随机选取。
 
 下面是用 `rand()` 及 `random_shuffle()` 编写的一个数据生成器。生成数据为 [「ZJOI2012」灾难](https://www.luogu.com.cn/problem/P2597) 的随机小数据。
 
@@ -121,9 +121,9 @@ int main() {
 
 ```cpp
 #include <algorithm>
-#include <random>
 #include <ctime>
 #include <iostream>
+#include <random>
 
 int a[100];
 
@@ -190,4 +190,4 @@ int main() {
 
 [^ref1]:  [Don't use rand(): a guide to random number generators in C++](https://codeforces.com/blog/entry/61587) 
 
-[^note1]: 版本号为 GCC 9.2.0
\ No newline at end of file
+[^note1]: 版本号为 GCC 9.2.0
-- 
2.11.0