随机化技巧

概述

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

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

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

记号和约定：

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

用随机集合覆盖目标元素

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

例：三部图的判定

问题

给定一张 $n$ 个结点、 $m$ 条边的简单无向图，用 RGB 三种颜色给每个结点染色满足任意一对邻居都不同色，或者报告无解。

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

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

对于所有异于 $C_{u}, C_{v}$ 的颜色 $X$ ，若 $u$ 被染成 $X$ ，则 $v$ 被染成 ${R, G, B} ∖ {X, C_{v}}$ 。

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

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

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

例：CodeChef SELEDGE

简要题意

给定一张点、边都有非负权值的无向图，找到一个大小 $\leq K$ 的边集合 $S$ ，以最大化与 $S$ 相连的点的权值和减去 $S$ 的边权和。一个点的权值只被计算一次。

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

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

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

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

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

考虑一张 $n$ 个点的菊花图，显然它有 2 种染色方案，所以它被染对颜色的概率是 $\frac{2}{2^{n}} = 2^{1 - n}$ 。
假设最优解中每个菊花的结点数分别为 $a_{1}, \dots, a_{l}$ ，则一定有 $(a_{1} - 1) + \dots + (a_{l} - 1) \leq K$ ，其中 $K$ 表示最多能够选出的边数。
从而所有菊花都被染对颜色的概率是 $2^{1 - a_{1}} \dots 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 (K^{2} (n + m))$ ，证明：

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

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

用随机元素命中目标集合

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

例：Gym 101550I

简要题意

有一张图形如：两条平行的链，加上连接两链的两条平行边。给定这张图上的若干条简单路径（每条路径表示一次通话），请你选择尽量少的边放置窃听器，以使得每条给定的路径上都有至少一个窃听器。

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

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

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

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

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

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

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

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

分析单次复杂度：

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

分析正确率：

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

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

例：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 \frac{(n - 1) (m - 1)}{n m}$ 。

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

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

理由：

\begin{aligned} \frac{(n - 1) (m - 1)}{n m} \cdot \frac{(n - 2) (m - 2)}{(n - 1) (m - 1)} \dots \frac{(n - k) (m - k)}{(n - k + 1) (m - k + 1)} \\ = \frac{(n - k) (m - k)}{n m} \\ \geq \frac{1}{4} \end{aligned}

而连续选完 $k$ 对 $(s, t)$ 后判断它们是否全部满足目标 I 很简单，只要再跑一遍强连通缩点，判断一下 $n, m$ 是否都减小了 $k$ 即可。注意到若每次减少 $k = \frac{min (n, m)}{2}$ ，则 $min (n, m)$ 必在 $O (\log (n + m))$ 轮内变成 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 ((| V | + | E |) \log | V |)$ 。

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

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

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

例：随机增量法

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

详见随机增量法。

例：TopCoder MagicMolecule 随机化解法

简要题意

给定一张 $n$ 个点、带点权的无向图，在其中所有大小不小于 $\frac{2 n}{3}$ 的团中，找到点权和最大的那个。

$n \leq 50$

不难想到折半搜索。把点集均匀分成左右两半 $V_{L}, V_{R}$ （大小都为 $\frac{n}{2}$ ），计算数组 $f_{L, k}$ 表示点集 $L \subseteq V_{L}$ 中的所有 $\geq k$ 元团的最大权值和。接着我们枚举右半边的每个团 $C_{R}$ ，算出左半边有哪些点与 $C_{R}$ 中的所有点相连（这个点集记作 $N_{L}$ ），并用 $f_{N_{L}, \frac{2}{3} n - | C_{R} |} + value (C_{R})$ 更新答案。

注意到可以 $O (1)$ 转移每一个 $f_{L, k}$ $f_{L,k}$ 。具体地说，取 $d$ 为 $L$ 中的任意一个元素，然后分类讨论：
- 假设最优解中 $d$ 不在团中，则从 $f_{L ∖ {d}, k}$ 转移而来。
- 假设最优解中 $d$ 在团中，则从 $f_{L \cap N (d), k} + value (d)$ 转移而来，其中 $N (d)$ 表示 $d$ 的邻居集合。
- 别忘了还要用 $f_{L, k + 1}$ 来更新 $f_{L, k}$ 。

这个解法会超时。尝试优化：

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

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

随机化用于哈希

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

简要题意

维护一棵动态变化的树，和一个动态变化的结点二元组集合。你需要支持：

删边、加边。保证得到的还是一棵树。
加入/删除某个结点二元组。
给定一条边 $e$ ，判断是否对于集合中的每个结点二元组 $(s, t)$ ， $e$ 都在 $s, t$ 间的简单路径上。

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

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

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

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

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

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

例：CodeChef PANIC 及其错误率分析

本题的大致解法：

可以证明[^ref1] $S (N)$ 服从一个关于 $N$ 的 $O (K)$ 阶线性递推式。
用 BM 算法求出该递推式。
借助递推式，用凯莱哈密顿定理计算出 $S (N)$ 。

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

问题

给定一个矩阵序列，该序列在模 $P := 998244353$ 意义下服从一个齐次线性递推式（递推式中的数乘和加法运算定义为矩阵的数乘和加法），求出最短递推式。

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

解决方案：给矩阵的每一位 $(i, j)$ 赋予一个 $

本页面最近更新：2023/6/27 13:39:08，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：TianyiQ, Enter-tainer, Tiphereth-A, Ir1d, leoleoasd, ouuan, billchenchina, CCXXXI, ImpleLee, ksyx, Marcythm, MegaOwIer, partychicken
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用