跳转至

随机化技巧

概述

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

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

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

记号和约定：

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

用随机集合覆盖目标元素

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

例：三部图的判定

问题

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

对每个点 \(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

简要题意

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

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

推论：最优解选出的边集，一定构成若干个不相交的菊花图（即直径不超过 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\)。

  • 理由：
\[ \begin{aligned} &\phantom{=\ }\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 \end{aligned} \]

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

算法伪代码 
1
2
3
4
5
6
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 随机化解法

简要题意

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

\(n\leq 50\)

不难想到折半搜索。把点集均匀分成左右两半 \(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,t)\)，\(e\) 都在 \(s,t\) 间的简单路径上。

对图中的每条边 \(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. 可以证明[^ref1] \(S(N)\) 服从一个关于 \(N\) 的 \(O(K)\) 阶线性递推式。
  2. 用 BM 算法求出该递推式。
  3. 借助递推式，用凯莱哈密顿定理计算出 \(S(N)\)。

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

问题

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

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

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

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, partychicken, ouuan, Marcythm, TianyiQ
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用