随机化技巧

概述¶

前置知识：随机函数 和 概率初步

本文将对 OI/ICPC 中的随机化相关技巧做一个简单的分类，并对每个分类予以介绍。本文也将介绍一些在 OI/ICPC 中很少使用，但与 OI/ICPC 在风格等方面较为贴近的方法，这些内容前将用 (*) 标注。

这一分类并不代表广泛共识，也必定不能囊括所有可能性，因此仅供参考。

记号和约定：

• \(\mathrm{Pr}[A]\) 表示事件 \(A\) 发生的概率。
• \(\mathrm{E}[X]\) 表示随机变量 \(X\) 的期望。
• 赋值号 \(:=\) 表示引入新的量，例如 \(Y:=1926\) 表示引入值为 \(1926\) 的量 \(Y\)。

用随机集合覆盖目标元素¶

庞大的解空间中有一个（或多个）解是我们想要的。我们可以尝试进行多次撒网，只要有一次能够网住目标解就能成功。

例：三部图的判定¶

对每个点 \(v\)，从 \(\{R,G,B\}\) 中等概率独立随机地选一种颜色 \(C_v\)，并钦定 \(v\) 不 被染成 \(C_v\)。最优解恰好符合这些限制的概率，显然是 \(\big(\frac 23\big)^n\)。

在这些限制下，对于一对邻居 \((u,v)\)，「\(u,v\) 不同色」的要求等价于以下这条「推出」关系：

• 对于所有异于 \(C_u,C_v\) 的颜色 \(X\)，若 \(u\) 被染成 \(X\)，则 \(v\) 被染成 \(\{R,G,B\}\setminus\{X,C_v\}\)。

于是我们可以对每个 \(v\) 设置布尔变量 \(B_v\)，其取值表示 \(v\) 被染成两种剩余的颜色中的哪一种。借助 2-SAT 模型即可以 \(O(n+m)\) 的复杂度解决这个问题。

这样做，单次的正确率是 \(\big(\frac 23\big)^n\)。将算法重复运行 \(-\big(\frac 32\big)^n\log \epsilon\) 次，只要有一次得到解就输出，这样即可保证 \(1-\epsilon\) 的正确率。（详见后文中「概率上界的分析」）

回顾：本题中「解空间」就是集合 \(\{R,G,B\}^n\)，我们每次通过随机施加限制来在一个缩小的范围内搜寻「目标解」——即合法的染色方案。

例：CodeChef SELEDGE¶

观察：如果选出的边中有三条边构成一条链，则删掉中间的那条一定不劣；如果选出的边中有若干条构成环，则删掉任何一条一定不劣。

推论：最优解选出的边集，一定构成若干个不相交的菊花图（即直径不超过 2 的树）。

推论：最优解选出的边集，一定构成一张二分图。

我们对每个点等概率独立随机地染上黑白两种颜色之一，并要求这一染色方案，恰好也是最优解所对应的二分图的黑白染色方案。

尝试计算最优解符合这一要求的概率：

• 考虑一张 \(n\) 个点的菊花图，显然它有 2 种染色方案，所以它被染对颜色的概率是 \(\dfrac 2{2^n}=2^{1-n}\)。
• 假设最优解中每个菊花的结点数分别为 \(a_1,\cdots,a_l\)，则一定有 \((a_1-1)+\cdots+(a_l-1)\leq K\)，其中 \(K\) 表示最多能够选出的边数。
• 从而所有菊花都被染对颜色的概率是 \(2^{1-a_1}\cdots 2^{1-a_l}\geq 2^{-K}\)。

在上述要求下，尝试建立费用流模型计算最优答案：

• 建立二分图，白点在左侧并与 \(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\big(K^2(n+m)\big)\)，证明：

• 首先，显然 SPFA 的运行次数 \(\leq K\)。
• 然后，在一次 SPFA 中，任何一个结点至多入队 \(O(K)\) 次。这是因为：
  • 任意时刻有流量的边不会超过 \(3K\) 条，否则就意味着在原图中选了超过 \(K\) 条边。
  • 对于任何一条长为 \(L\) 的增广路，其中至少有 \(\dfrac L2-2\) 条边是某条有流量的边的反向边，因为正向边都是从图的左侧指向右侧，只有这些反向边才会从右侧指向左侧。
  • 综合以上两条，得到任意一条增广路的长度不超过 \(6K+4\)。
• 综上，复杂度是 \(O\big(K^2(n+m)\big)\)。

和上一题类似，我们需要把整个过程重复 \(-2^K \log\epsilon\) 次以得到 \(1-\epsilon\) 的正确率。总复杂度 \(O\big(2^KK^2(n+m)\cdot -\log\epsilon\big)\)。

用随机元素命中目标集合¶

我们需要确定一个集合中的任意一个元素，为此我们随机选取元素，以期能够恰好命中这一集合。

例：Gym 101550I¶

整张图可以拆分为一个环加上四条从环伸出去的链。对于这四条链中的任何一条（记作 \(C\)），考虑在这条链上如何放置窃听器，容易通过贪心算法得到满足以下条件的方案：

• 在拦截所有 \(C\) 内部进行的通话的前提下，用的窃听器数量最少。
• 在上一条的前提下，使得 \(C\) 上的窃听器离环的最短距离尽可能小。
  • 作这一要求的目的是尽可能地拦截恰有一个端点在 \(C\) 内部的通话。

接着考虑链与环相接处的共计 4 条边，我们暴力枚举这些边上有没有放窃听器。显然，如果想要拦截跨越链和环的通话，在这 4 条边上放窃听器一定是最优的。现在，我们可以把通话线路分为以下几种：

1. 完全在链上的通话线路。这些线路一定已经被拦截，故可以忽略。
2. 跨越链和环，且已经被拦截的通话线路。它们可以忽略。
3. 跨越链和环，且未被拦截的通话线路。我们可以直接截掉它在链上的部分（因为链上的窃听器放置方案已经固定了），只保留环上的部分。
4. 完全在环上的通话线路。

至此，问题转化成了环上的问题。

设最优解中在环上的边集 \(S\) 上放置了窃听器，如果我们已经确定了 \(S\) 中的任何一个元素 \(e\)，就可以：

• 先在 \(e\) 处断环为链。
• 然后从 \(e\) 开始贪心，不断找到下一个放置窃听器的边。注意到如果经过合适的预处理，贪心的每一步可以做到 \(O(1)\) 的复杂度。
• 从而以 \(O(|S|)\) 的复杂度解决问题。

我们考虑随机选取环上的一条边 \(e'\)，并钦定 \(e'\in S\) 再执行上述过程，重复多次取最优。

分析单次复杂度：

• 观察：记 \(S'\) 表示所有选取了 \(e'\) 的方案中的最优解，则 \(|S'|\leq |S|+1\)。
• 从而单次复杂度 \(O(|S'|)=O(|S|)\)。

分析正确率：

• 显然单次正确率 \(\dfrac {|S|}n\)，其中 \(n\) 表示环长。
• 所以需要重复 \(-\dfrac n{|S|}\log\epsilon\) 次以得到 \(1-\epsilon\) 的正确率。

综上，该算法的复杂度 \(O\big(|S|\cdot -\dfrac n{|S|}\log\epsilon\big)=O(-n\log\epsilon)\)。

例：CSES 1685 New Flight Routes¶

先对原图进行强连通缩点。我们的目标显然是使每个汇点能到达每个源点。

不难证明，我们一定只会从汇点到源点连边，因为任何其他的连边，都能对应上一条不弱于它的、从汇点到源点的连边。

我们的一个核心操作是，取汇点 \(t\) 和源点 \(s\)（它们不必在同一个弱连通分量里），连边 \(t\to s\) 以 使得 \(s\) 和 \(t\) 都不再是汇点或源点（记作目标 I）。理想情况下这种操作每次能减少一个汇点和一个源点，那我们不断操作直到只剩一个汇点或只剩一个源点，而这样的情形就很平凡了。由此，我们猜测答案是源点个数与汇点个数的较大值。

不难发现，上述操作能够达到目标 I 的充要条件是：\(t\) 拥有 \(s\) 以外的前驱、且 \(s\) 拥有 \(t\) 以外的后继。可以证明（等会会给出证明），对于任意一张有着至少两个源点和至少两个汇点的 DAG，都存在这样的 \((s,t)\)；但存在性的结论无法帮助我们构造方案，还需做其他分析。

• 有了这个充要条件还难以直接得到算法，主要的原因是连边 \(t\to s\) 后可能影响其他 \((s',t')\) 二元组的合法性，这个比较难处理。

注意到我们关于源汇点间的关系知之甚少（甚至连快速查询一对 \(s-t\) 间是否可达都需要 dfs + bitset 预处理，而时限并不允许这么做），这提示我们需要某种非常一般和强大的性质。

观察：不满足目标 I 的 \((s,t)\) 至多有 \(n+m-1\) 对，其中 \(n\) 表示源点个数，\(m\) 表示汇点个数。

• 理由：对于每一对这样的 \((s,t)\)，若把它看成 \(s,t\) 间的一条边，则所有这些边构成的图形如若干条不相交的链，于是边数不超过点数减一。
• 作出这一观察的动机是，要想将存在性结论应用于算法，前置步骤往往是把定性的结果加强为定量的结果。

推论：等概率随机选取 \((s,t)\)，满足前述要求的概率 \(\geq \dfrac {(n-1)(m-1)}{nm}\)。

• 注意到这个结论严格强于先前给出的存在性结论。

推论：等概率独立随机地连续选取 \(\dfrac {\min(n,m)}2\) 对不含公共元素的 \((s,t)\)，并对它们 依次 操作（即连边 \(t\to s\)），则这些操作全部满足目标 I 的概率 \(\geq \dfrac 14\)。

• 理由：

而连续选完 \(k\) 对 \((s,t)\) 后判断它们是否全部满足目标 I 很简单，只要再跑一遍强连通缩点，判断一下 \(n,m\) 是否都减小了 \(k\) 即可。注意到若每次减少 \(k=\dfrac{\min(n,m)}2\)，则 \(\min(n,m)\) 必在 \(O\big(\log(n+m)\big)\) 轮内变成 1，也就转化到了平凡的情况。

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\big((|V|+|E|) \log |V|\big)\)。

回顾：我们需要确定任意一对能够实现目标 I 的二元组 \((s,t)\)，为此我们随机选择 \((s,t)\)。

用随机化获得随机数据的性质¶

如果一道题的数据随机生成，我们可能可以利用随机数据的性质解决它。而在有些情况下，即使数据并非随机生成，我们也可以通过随机化来给其赋予随机数据的某些特性，从而帮助解决问题。

例：随机增量法¶

随机生成的元素序列可能具有「前缀最优解变化次数期望下很小」等性质，而随机增量法就通过随机打乱输入的序列来获得这些性质。

详见 随机增量法。

例：TopCoder MagicMolecule 随机化解法¶

不难想到折半搜索。把点集均匀分成左右两半 \(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\) 中的任意一个元素，然后分类讨论：
  • 假设最优解中 \(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}|\) 可能是奇数。简单起见，这里假设它是偶数；奇数的情况对解法没有本质改变。
  • 实验发现，随机尝试约 20 次就能以很大概率有至少一次满足该性质。也就是说，如果我们的算法依赖于「\(C_{res}\) 被平分」这一性质，则将算法重复执行 20 次取最优，同样也能保证以很大概率得到正确答案。
• 有了这一性质，我们就可以直接钦定左侧团 \(L\)、右侧团 \(C_R\) 的大小都 \(\geq \dfrac n3\)。这会对复杂度带来两处改进：
  • \(f\) 可以省掉记录大小的维度。
  • 因为只需考虑大小 \(\geq \dfrac n3\) 的团，所以需要考虑的左侧团 \(L\) 和 右侧团 \(C_R\) 的数量也大大减少至约 \(1.8\cdot 10^6\)。
• 现在的瓶颈变成了求单侧的某一子集的权值和，因为这需要 \(O\big(2^{|V_L|}+2^{|V_R|}\big)\) 的预处理。
  • 解决方案：在 \(V_L,V_R\) 内部再次折半；当查询一个子集的权值和时，将这个子集分成左右两半查询，再把答案相加。
• 这样即可通过本题。

回顾：一个随机的集合有着「在划分出的两半的数量差距不会太悬殊」这一性质，而我们通过随机划分获取了这个性质。

随机化用于哈希¶

例：UOJ #207 共价大爷游长沙¶

对图中的每条边 \(e\)，我们定义集合 \(S_e\) 表示经过该边的关键路径（即题中的 \((a,b)\)）集合。考虑对每条边动态维护集合 \(S_e\) 的哈希值，这样就能轻松判定 \(S_e\) 是否等于全集（即 \(e\) 是否是「必经之路」）。

哈希的方式是，对每个 \((a,b)\) 赋予 \(2^{64}\) 以内的随机非负整数 \(H_{(a,b)}\)，然后一个集合的哈希值就是其中元素的 \(H\) 值的异或和。

这样的话，任何一个固定的集合的哈希值一定服从 \(R:=\left\{0,1,\cdots,2^{64}-1\right\}\) 上的均匀分布（换句话说，哈希值的取值范围为 \(R\)，且取每一个值的概率相等）。这是因为：

1. 单个 \(H_{(a,b)}\) 显然服从均匀分布。
2. 两个独立且服从 \(R\) 上的均匀分布的随机变量的异或和，一定也服从 \(R\) 上的均匀分布。自证不难。

从而该算法的正确率是有保障的。

至于如何维护这个哈希值，使用 LCT 即可。

例：CodeChef PANIC 及其错误率分析¶

本题的大致解法：

1. 可以证明¹ \(S(N)\) 服从一个关于 \(N\) 的 \(O(K)\) 阶线性递推式。
2. 用 BM 算法求出该递推式。
3. 借助递推式，用凯莱哈密顿定理计算出 \(S(N)\)。

这里仅关注第二部分，即如何求一个矩阵序列的递推式。所以我们只需考虑下述问题：

如果一系列矩阵服从一个递推式 \(F\)，那么它的每一位也一定服从 \(F\)。然而，如果对某一位求出最短递推式 \(F'\)，则 \(F'\) 可能会比 \(F\) 更短，从而产生问题。

解决方案：给矩阵的每一位 \((i,j)\) 赋予一个 \(<P\) 的随机权值 \(x_{i,j}\)，然后对于序列中每个矩阵计算其所有位的加权和模 \(P\) 的结果，再把每个矩阵算出的这个数连成一个数列，最后我们对所得数列运行 BM 算法。

错误率分析：

• 假设上述做法求得了不同于 \(F\)（且显然也不长于 \(F\)）的 \(l\) 阶递推式 \(F'\)。
• 因为矩阵序列不服从 \(F'\)，所以一定存在矩阵中的某个位置 \((i,j)\)，满足该位置对应的数列 \(S_{i,j}\) 在某个 \(N\) 处不服从 \(F'\)。也就是说：

• 假设 \((i,j)\) 是唯一的不服从的位置，则一定有：

• 显然这仅当 \(x_{i,j}=0\) 时才成立，概率 \(P^{-1}\)。
• 如果有多个不服从的位置呢？
  • 对每个这样的位置 \((i,j)\)，易证 \(T_{i,j}\) 服从 \(R:=\{0,1,\cdots,P-1\}\) 上的均匀分布。
  • 若干个互相独立的、服从 \(R\) 上的均匀分布的随机变量，它们在模意义下的和，依然服从 \(R\) 上的均匀分布。自证不难。
  • 从而这种情况下的错误率也是 \(P^{-1}\)。

例：UOJ #552 同构判定鸭 及其错误率分析¶

令 \(f_{K,i,j}\) 表示图 \(G_K\) 中从点 \(i\) 开始的所有长为 \(j\) 的路径，这些路径对应的所有字符串构成的多重集的哈希值。按照 \(j\) 升序考虑每个状态，转移时枚举 \(i\) 的出边并钦定该边为路径上的第一条边。

要判断是否存在长度 \(=L\) 的坏串，只需把 \(\{f_{0,*,L}\}\) 和 \(\{f_{1,*,L}\}\) 各自「整合」起来再比较即可（通配符 * 这里表示每一个结点，例如 \(\{f_{0,*,L}\}\) 表示全体 \(f_{0,i,L}\) 构成的集合，其中 \(i\) 取遍所有结点）。官方题解²中证明了最短坏串（如果存在的话）长度一定不超过 \(n_1+n_2\)，所以这个解法的复杂度是可靠的。

接下来考虑具体的哈希方式。注意到常规的哈希方法——即把串 \(a_1a_2\cdots a_k\) 映射到 \(\big(a_1+Pa_2+P^2a_3+\cdots+P^{k-1}a_k\big)\bmod Q\) 上、再把多重集的哈希值定为其中元素的哈希值之和模 \(Q\)——在这里是行不通的。一个反例是，集合 {"ab","cd"} 与集合 {"cb","ad"} 的哈希值是一样的，不论 \(P,Q\) 如何取值。

上述做法的问题在于，一个串的哈希值是一个和式，从而其中的每一项可以拆出来并重组。为避免这一问题，我们考虑把哈希值改为一个连乘式。此外，乘法交换律会使得不同的位不可区分，为避免这一点我们要为不同的位赋予不同的权值。

对每一个二元组 \((c,j)\)（其中 \(c\) 为字符，\(j\) 为整数表示 \(c\) 在某个串中的第几位）我们都预先生成一个随机数 \(x_{c,j}\)。然后我们把串 \(a_1a_2\cdots a_k\) 映射到 \(x_{a_1,1}x_{a_2,2}\cdots x_{a_k,k}\bmod Q\) 上（其中 \(Q\) 为 随机选取 的质数）、再把多重集的哈希值定为其中元素的哈希值之和模 \(Q\)。接下来分析它的错误率。

记 \(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\pmod {Q}\)，即 \(P_0,P_1\) 的每一项系数在模 \(Q\) 意义下都对应相等。
2. \(P_0\not\equiv P_1\pmod {Q}, P_0(x_{*,*})\equiv P_1(x_{*,*})\pmod {Q}\)，即 \(P_0,P_1\) 虽然不恒等，但我们选取的这一组 \(\{x_{*,*}\}\) 恰好使得它们在此处的点值相等。

分析前者发生的概率：

• 观察：对于任意的 \(A\neq B; A,B\leq N\) 和随机选取的质数 \(Q\leq Q_{\max}\)，一定有：

• 这是因为：使 \(A\equiv B\) 成立的 \(Q\) 一定满足 \(Q\big|(A-B)\)，这样的 \(Q\) 有 \(\omega(A-B)\leq \log_2 N\) 个；而由质数定理，\(Q_{\max}\) 以内不同的质数又有 \(\Theta\Big(\dfrac {Q_{\max}}{\log Q_{\max}}\Big)\) 个。将两者相除即可得到上式。
• 在上述观察中取 \(A,B\)（满足 \(A\neq B\)）为某一特定项在 \(P_0,P_1\) 中的系数（也就等于该项对应的串在 \(G_0,G_1\) 中的出现次数），则易见 \(A,B\leq (m_1+m_2)^{L}\)，得到：

• 所以取 \(Q_{\max}\approx 10^{12}\) 就绰绰有余。如果机器无法支持这么大的整数运算，可以用双哈希代替。

分析后者发生的概率：

• 在 Schwartz–Zippel 引理中：
  • 取域 \(F\) 为模 \(Q\) 的剩余系对应的域
  • 取 \(f(x_{*,*})=P_0(x_{*,*})-P_1(x_{*,*})\) 为 \(L\) 次非零多项式
  • 取 \(S=F\)
• 得到：所求概率 \(\leq \dfrac LQ\)。

注意到我们需要对每个 \(L\) 都能保证正确性，所以要想保证严谨的话还需用 Union Bound（见后文）说明一下。

实践上我们不必随机选取模数，因为——比如说——用自己的生日做模数的话，实际上已经相当于随机数了。

例：（*）子矩阵不同元素个数¶

引理：令 \(X_{1\cdots k}\) 为互相独立的随机变量，且取值在 \([0,1]\) 中均匀分布，则 \(\mathrm{E}\big[\min\limits_i X_i\big]=\dfrac 1{k+1}\)。

• 证明：考虑一个单位圆，其上分布着 相对位置 均匀随机的 \(k+1\) 个点，分别在位置 \(0,X_1,X_2,\cdots,X_k\) 处。那么 \(\min\limits_i X_i\) 就等于 \(k+1\) 段空隙中特定的一段的长度。而因为这些空隙之间是「对称」的，所以其中任何一段特定空隙的期望长度都是 \(\dfrac 1{k+1}\)。

我们取 \(k\) 为不同元素的个数，并借助上述引理来从 \(\min\limits_i X_i\) 反推得到 \(k\)。

考虑采用某个哈希函数，将矩阵中每个元素都均匀、独立地随机映射到 \([0,1]\) 中的实数上去，且相等的元素会映射到相等的实数。这样的话，一个子矩阵中的所有元素对应的那些实数，在去重后就恰好是先前的集合 \(\{X_1,\cdots,X_k\}\) 的一个实例，其中 \(k\) 等于子矩阵中不同元素的个数。

于是我们得到了算法：

1. 给矩阵中元素赋 \([0,1]\) 中的哈希值。为保证随机性，哈希函数可以直接用 map 和随机数生成器实现，即每遇到一个新的未出现过的值就给它随机一个哈希值。
2. 回答询问时设法求出子矩阵中哈希值的最小值 \(M\)，并输出 \(\dfrac 1M-1\)。

然而，这个算法并不能令人满意。它的输出值的期望是 \(\mathrm{E}\Big[\dfrac 1{\min\limits_i X_i}-1\Big]\)，但事实上这个值并不等于 \(\dfrac 1{\mathrm{E}\big[\min\limits_i X_i\big]}-1=k\)，而（可以证明）等于 \(\infty\)。

也就是说，我们不能直接把 \(\min\limits_i X_i\) 的单次取值放在分母上，而要先算得它的期望，再把期望值放在分母上。

怎么算期望值？多次随机取平均。

我们用 \(C\) 组不同的哈希函数分别执行前述过程，回答询问时计算出 \(C\) 个不同的 \(M\) 值，并算出其平均数 \(\overline M\)，然后输出 \(\big(\overline M\big)^{-1}-1\)。

实验发现取 \(C\approx 80\) 即可满足要求。严格证明十分繁琐，在此略去。

最后，怎么求子矩阵最小值？用二维 S-T 表即可，预处理 \(O(nm\log n\log m)\)，回答询问 \(O(1)\)。

随机化在算法中的其他应用¶

随机化的其他作用还包括：

• 防止被造数据者用针对性数据卡掉。例如在搜索时随机打乱邻居的顺序。
• 保证算法过程中进行的「操作」具有（某种意义上的）均匀性。例如 模拟退火 算法。

在这些场景下，随机化常常（但并不总是）与乱搞、骗分等做法挂钩。

例：「TJOI2015」线性代数¶

本题的标准算法是网络流，但这里我们采取这样的乱搞做法：

• 每次随机一个位置，把这个位置取反，判断大小并更新答案。

#include <algorithm>
#include <cstdlib>
#include <iostream>

int n;

int a[510], b[510], c[510][510], d[510];
int p[510], q[510];

int maxans = 0;

void check() {
  memset(d, 0, sizeof d);
  int nowans = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) d[i] += a[j] * c[i][j];
  for (int i = 1; i <= n; i++) nowans += (d[i] - b[i]) * a[i];
  maxans = std::max(maxans, nowans);
}

int main() {
  srand(19260817);
  std::cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) std::cin >> c[i][j];
  for (int i = 1; i <= n; i++) std::cin >> b[i];
  for (int i = 1; i <= n; i++) a[i] = 1;
  check();
  for (int T = 1000; T; T--) {
    int tmp = rand() % n + 1;
    a[tmp] ^= 1;
    check();
  }
  std::cout << maxans << '\n';
}

例：（*）随机堆³¶

可并堆最常用的写法应该是左偏树了，通过维护树高让树左偏来保证合并的复杂度。然而维护树高有点麻烦，我们希望尽量避开。

那么可以考虑使用随机堆，即不按照树高来交换儿子，而是随机交换。

struct Node {
  int child[2];
  long long val;
} nd[100010];

int root[100010];

int merge(int u, int v) {
  if (!(u && v)) return u | v;
  int x = rand() & 1, p = nd[u].val > nd[v].val ? u : v;
  nd[p].child[x] = merge(nd[p].child[x], u + v - p);
  return p;
}

void pop(int &now) { now = merge(nd[now].child[0], nd[now].child[1]); }

随机堆对堆的形态没有任何硬性或软性的要求，合并操作的期望复杂度对任何两个堆（作为 merge 函数的参数）都成立。下证。

与随机性有关的证明技巧¶

以下列举几个比较有用的技巧。

自然，这寥寥几项不可能就是全部；如果你了解某种没有列出的技巧，那么欢迎补充。

概率上界的分析¶

详见 概率不等式 页面。

除了上述页面中提到的各种不等式外，推导过程中还经常会用到以下结论：

自然常数的使用：\(\Big(1-\dfrac{1}{n}\Big)^n\leq \dfrac{1}{\mathrm{e}},\forall n\geq1\)

• 左式关于 \(n\geq 1\) 单调递增且在 \(+\infty\) 处的极限是 \(\dfrac{1}{\mathrm{e}}\)，因此有这个结论。
• 这告诉我们，如果 \(n\) 个互相独立的事件，每个的发生概率为 \(1-\dfrac 1n\)，则它们全部发生的概率至多为 \(\dfrac{1}{\mathrm{e}}\)。

「耦合」思想¶

「耦合」思想常用于同时处理超过一个有随机性的对象，或者同时处理随机的对象和确定性的对象。

引子：随机图的连通性¶

这个结论看起来再自然不过，但严格证明却并不那么容易。

这一段证明中用到的思想被称为「耦合」，可以从字面意思来理解这种思想。本例中它体现为把两个本来独立的随机过程合二为一。

应用：NERC 2019 Problem G: Game Relics¶

观察：如果选择抽物品，就一定会一直抽直到获得新物品为止。

• 理由：如果抽一次没有获得新物品，则新的局面和抽物品之前的局面一模一样，所以如果旧局面的最优行动是「抽一发」，则新局面的最优行动一定也是「再抽一发」。

我们可以计算出 \(f_k\) 表示：如果当前已经拥有 \(k\) 个不同物品，则期望要花多少钱才能抽到新物品。根据刚才的观察，我们可以直接把 \(f_k\) 当作一个固定的代价，即转化为「每次花 \(f_k\) 块钱随机获得一个新物品」。

结论：最优策略一定是先抽若干次，再买掉所有没抽到的物品。

这个结论符合直觉，因为 \(f_k\) 是关于 \(k\) 递增的，早抽似乎确实比晚抽看起来好一点。

基于这个结论，我们再次等价地转化问题：把「选一个物品并支付对应价格购买」的操作，改成「随机选一个未拥有的物品并支付对应价格购买」。等价性的理由是，既然购买只是用来扫尾的，那选到哪个都无所谓。

现在我们发现，「抽取」和「购买」，实质上已经变成了相同的操作，区别仅在于付出的价格不同。选择购买还是抽取，对于获得物品的顺序毫无影响，而且每种获得物品的顺序都是等可能的。

观察：在某一时刻，我们应当选择买，当且仅当下一次抽取的代价（由已经抽到的物品数确定）大于剩余物品的平均价格（等于的话则任意）。

• 可以证明，随着时间的推移，抽取代价的增速一定不低于剩余物品均价的增速。这说明从抽到买的「临界点」只有一个，进一步验证了先前结论。

最后，我们枚举所有可能的局面（即已经拥有的元素集合），算出这种局面出现的概率（已有元素的排列方案数除以总方案数），乘上当前局面最优决策的代价（由拥有元素个数和剩余物品总价确定），再加起来即可。这个过程可以用背包式的 DP 优化，即可通过本题。

回顾：可以看到，耦合的技巧在本题中使用了两次。第一次是在证明过程中，令两个随机过程使用同一个随机源；第二次是把购买转化成随机购买（即引入随机源），从而使得购买和抽取这两种操作实质上「耦合」为同一种操作（即令抽取和购买操作共享一个随机源）。

参考资料¶