随机化技巧
概述
前置知识:随机函数 和 概率初步
本文将对 OI/ICPC 中的随机化相关技巧做一个简单的分类,并对每个分类予以介绍。本文也将介绍一些在 OI/ICPC 中很少使用,但与 OI/ICPC 在风格等方面较为贴近的方法,这些内容前将用 (*)
标注。
这一分类并不代表广泛共识,也必定不能囊括所有可能性,因此仅供参考。
记号和约定:
- Pr[𝐴]
表示事件 𝐴
发生的概率。 - E[𝑋]
表示随机变量 𝑋
的期望。 - 赋值号 :=
表示引入新的量,例如 𝑌 :=1926
表示引入值为 1926
的量 𝑌
。
用随机集合覆盖目标元素
庞大的解空间中有一个(或多个)解是我们想要的。我们可以尝试进行多次撒网,只要有一次能够网住目标解就能成功。
例:三部图的判定
问题
给定一张 𝑛
个结点、𝑚
条边的简单无向图,用 RGB 三种颜色给每个结点染色 满足任意一对邻居都不同色,或者报告无解。
对每个点 𝑣
,从 {𝑅,𝐺,𝐵}
中等概率独立随机地选一种颜色 𝐶𝑣
,并钦定 𝑣
不 被染成 𝐶𝑣
。最优解恰好符合这些限制的概率,显然是 (23)𝑛
。
在这些限制下,对于一对邻居 (𝑢,𝑣)
,「𝑢,𝑣
不同色」的要求等价于以下这条「推出」关系:
- 对于所有异于 𝐶𝑢,𝐶𝑣
的颜色 𝑋
,若 𝑢
被染成 𝑋
,则 𝑣
被染成 {𝑅,𝐺,𝐵} ∖{𝑋,𝐶𝑣}
。
于是我们可以对每个 𝑣
设置布尔变量 𝐵𝑣
,其取值表示 𝑣
被染成两种剩余的颜色中的哪一种。借助 2-SAT 模型即可以 𝑂(𝑛 +𝑚)
的复杂度解决这个问题。
这样做,单次的正确率是 (23)𝑛
。将算法重复运行 −(32)𝑛log𝜖
次,只要有一次得到解就输出,这样即可保证 1 −𝜖
的正确率。(详见后文中「概率上界的分析」)
回顾:本题中「解空间」就是集合 {𝑅,𝐺,𝐵}𝑛
,我们每次通过随机施加限制来在一个缩小的范围内搜寻「目标解」——即合法的染色方案。
简要题意
给定一张点、边都有非负权值的无向图,找到一个大小 ≤𝐾
的边集合 𝑆
,以最大化与 𝑆
相连的点的权值和减去 𝑆
的边权和。一个点的权值只被计算一次。
观察:如果选出的边中有三条边构成一条链,则删掉中间的那条一定不劣;如果选出的边中有若干条构成环,则删掉任何一条一定不劣。
推论:最优解选出的边集,一定构成若干个不相交的菊花图(即直径不超过 2 的树)。
推论:最优解选出的边集,一定构成一张二分图。
我们对每个点等概率独立随机地染上黑白两种颜色之一,并要求这一染色方案,恰好也是最优解所对应的二分图的黑白染色方案。
尝试计算最优解符合这一要求的概率:
- 考虑一张 𝑛
个点的菊花图,显然它有 2 种染色方案,所以它被染对颜色的概率是 22𝑛 =21−𝑛
。 - 假设最优解中每个菊花的结点数分别为 𝑎1,⋯,𝑎𝑙
,则一定有 (𝑎1 −1) +⋯ +(𝑎𝑙 −1) ≤𝐾
,其中 𝐾
表示最多能够选出的边数。 - 从而所有菊花都被染对颜色的概率是 21−𝑎1⋯21−𝑎𝑙 ≥2−𝐾
。
在上述要求下,尝试建立费用流模型计算最优答案:
- 建立二分图,白点在左侧并与 𝑆
相连,黑点在右侧并与 𝑇
相连。- 对于白点 𝑣
,从 𝑆
向它连一条容量为 1、费用为 −𝐴𝑣
的边,和一条容量为 ∞
、费用为 0 的边。 - 对于黑点 𝑣
,从它向 𝑇
连一条容量为 1、费用为 −𝐴𝑣
的边,和一条容量为 ∞
、费用为 0 的边。
- 对于原图中的边 (𝑢,𝑣,𝐵)
满足 𝑢
为白色、𝑣
为黑色,连一条从 𝑢
到 𝑣
的边,容量为 1,费用为 𝐵
。 - 在该图中限制流量不超过 𝐾
,则最小费用的相反数就是答案。
用 SPFA 费用流求解的话,复杂度是 𝑂(𝐾2(𝑛 +𝑚))
,证明:
- 首先,显然 SPFA 的运行次数 ≤𝐾
。 - 然后,在一次 SPFA 中,任何一个结点至多入队 𝑂(𝐾)
次。这是因为:- 任意时刻有流量的边不会超过 3𝐾
条,否则就意味着在原图中选了超过 𝐾
条边。 - 对于任何一条长为 𝐿
的增广路,其中至少有 𝐿2 −2
条边是某条有流量的边的反向边,因为正向边都是从图的左侧指向右侧,只有这些反向边才会从右侧指向左侧。 - 综合以上两条,得到任意一条增广路的长度不超过 6𝐾 +4
。
- 综上,复杂度是 𝑂(𝐾2(𝑛 +𝑚))
。
和上一题类似,我们需要把整个过程重复 −2𝐾log𝜖
次以得到 1 −𝜖
的正确率。总复杂度 𝑂(2𝐾𝐾2(𝑛 +𝑚) ⋅ −log𝜖)
。
用随机元素命中目标集合
我们需要确定一个集合中的任意一个元素,为此我们随机选取元素,以期能够恰好命中这一集合。
简要题意
有一张图形如:两条平行的链,加上连接两链的两条平行边。给定这张图上的若干条简单路径(每条路径表示一次通话),请你选择尽量少的边放置窃听器,以使得每条给定的路径上都有至少一个窃听器。
整张图可以拆分为一个环加上四条从环伸出去的链。对于这四条链中的任何一条(记作 𝐶
),考虑在这条链上如何放置窃听器,容易通过贪心算法得到满足以下条件的方案:
- 在拦截所有 𝐶
内部进行的通话的前提下,用的窃听器数量最少。 - 在上一条的前提下,使得 𝐶
上的窃听器离环的最短距离尽可能小。- 作这一要求的目的是尽可能地拦截恰有一个端点在 𝐶
内部的通话。
接着考虑链与环相接处的共计 4 条边,我们暴力枚举这些边上有没有放窃听器。显然,如果想要拦截跨越链和环的通话,在这 4 条边上放窃听器一定是最优的。现在,我们可以把通话线路分为以下几种:
- 完全在链上的通话线路。这些线路一定已经被拦截,故可以忽略。
- 跨越链和环,且已经被拦截的通话线路。它们可以忽略。
- 跨越链和环,且未被拦截的通话线路。我们可以直接截掉它在链上的部分(因为链上的窃听器放置方案已经固定了),只保留环上的部分。
- 完全在环上的通话线路。
至此,问题转化成了环上的问题。
设最优解中在环上的边集 𝑆
上放置了窃听器,如果我们已经确定了 𝑆
中的任何一个元素 𝑒
,就可以:
- 先在 𝑒
处断环为链。 - 然后从 𝑒
开始贪心,不断找到下一个放置窃听器的边。注意到如果经过合适的预处理,贪心的每一步可以做到 𝑂(1)
的复杂度。 - 从而以 𝑂(|𝑆|)
的复杂度解决问题。
我们考虑随机选取环上的一条边 𝑒′
,并钦定 𝑒′ ∈𝑆
再执行上述过程,重复多次取最优。
分析单次复杂度:
- 观察:记 𝑆′
表示所有选取了 𝑒′
的方案中的最优解,则 |𝑆′| ≤|𝑆| +1
。 - 从而单次复杂度 𝑂(|𝑆′|) =𝑂(|𝑆|)
。
分析正确率:
- 显然单次正确率 |𝑆|𝑛
,其中 𝑛
表示环长。 - 所以需要重复 −𝑛|𝑆|log𝜖
次以得到 1 −𝜖
的正确率。
综上,该算法的复杂度 𝑂(|𝑆| ⋅ −𝑛|𝑆|log𝜖) =𝑂( −𝑛log𝜖)
。
简要题意
给定一张有向图,请你加最少的边使得该图强连通,需 输出方案。
先对原图进行强连通缩点。我们的目标显然是使每个汇点能到达每个源点。
不难证明,我们一定只会从汇点到源点连边,因为任何其他的连边,都能对应上一条不弱于它的、从汇点到源点的连边。
我们的一个核心操作是,取汇点 𝑡
和源点 𝑠
(它们不必在同一个弱连通分量里),连边 𝑡 →𝑠
以 使得 𝑠
和 𝑡
都不再是汇点或源点(记作目标 I)。理想情况下这种操作每次能减少一个汇点和一个源点,那我们不断操作直到只剩一个汇点或只剩一个源点,而这样的情形就很平凡了。由此,我们猜测答案是源点个数与汇点个数的较大值。
不难发现,上述操作能够达到目标 I 的充要条件是:𝑡
拥有 𝑠
以外的前驱、且 𝑠
拥有 𝑡
以外的后继。可以证明(等会会给出证明),对于任意一张有着至少两个源点和至少两个汇点的 DAG,都存在这样的 (𝑠,𝑡)
;但存在性的结论无法帮助我们构造方案,还需做其他分析。
- 有了这个充要条件还难以直接得到算法,主要的原因是连边 𝑡 →𝑠
后可能影响其他 (𝑠′,𝑡′)
二元组的合法性,这个比较难处理。
注意到我们关于源汇点间的关系知之甚少(甚至连快速查询一对 𝑠 −𝑡
间是否可达都需要 dfs + bitset 预处理,而时限并不允许这么做),这提示我们需要某种非常一般和强大的性质。
观察:不满足目标 I 的 (𝑠,𝑡)
至多有 𝑛 +𝑚 −1
对,其中 𝑛
表示源点个数,𝑚
表示汇点个数。
- 理由:对于每一对这样的 (𝑠,𝑡)
,若把它看成 𝑠,𝑡
间的一条边,则所有这些边构成的图形如若干条不相交的链,于是边数不超过点数减一。 - 作出这一观察的动机是,要想将存在性结论应用于算法,前置步骤往往是把定性的结果加强为定量的结果。
推论:等概率随机选取 (𝑠,𝑡)
,满足前述要求的概率 ≥(𝑛−1)(𝑚−1)𝑛𝑚
。
推论:等概率独立随机地连续选取 min(𝑛,𝑚)2
对不含公共元素的 (𝑠,𝑡)
,并对它们 依次 操作(即连边 𝑡 →𝑠
),则这些操作全部满足目标 I 的概率 ≥14
。
= (𝑛−1)(𝑚−1)𝑛𝑚⋅(𝑛−2)(𝑚−2)(𝑛−1)(𝑚−1)⋯(𝑛−𝑘)(𝑚−𝑘)(𝑛−𝑘+1)(𝑚−𝑘+1)=(𝑛−𝑘)(𝑚−𝑘)𝑛𝑚≥14
而连续选完 𝑘
对 (𝑠,𝑡)
后判断它们是否全部满足目标 I 很简单,只要再跑一遍强连通缩点,判断一下 𝑛,𝑚
是否都减小了 𝑘
即可。注意到若每次减少 𝑘 =min(𝑛,𝑚)2
,则 min(𝑛,𝑚)
必在 𝑂(log(𝑛+𝑚))
轮内变成 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()
|
复杂度 𝑂((|𝑉| +|𝐸|)log|𝑉|)
。
回顾:我们需要确定任意一对能够实现目标 I 的二元组 (𝑠,𝑡)
,为此我们随机选择 (𝑠,𝑡)
。
用随机化获得随机数据的性质
如果一道题的数据随机生成,我们可能可以利用随机数据的性质解决它。而在有些情况下,即使数据并非随机生成,我们也可以通过随机化来给其赋予随机数据的某些特性,从而帮助解决问题。
例:随机增量法
随机生成的元素序列可能具有「前缀最优解变化次数期望下很小」等性质,而随机增量法就通过随机打乱输入的序列来获得这些性质。
详见 随机增量法。
简要题意
给定一张 𝑛
个点、带点权的无向图,在其中所有大小不小于 2𝑛3
的团中,找到点权和最大的那个。
𝑛 ≤50
不难想到折半搜索。把点集均匀分成左右两半 𝑉𝐿,𝑉𝑅
(大小都为 𝑛2
),计算数组 𝑓𝐿,𝑘
表示点集 𝐿 ⊆𝑉𝐿
中的所有 ≥𝑘
元团的最大权值和。接着我们枚举右半边的每个团 𝐶𝑅
,算出左半边有哪些点与 𝐶𝑅
中的所有点相连(这个点集记作 𝑁𝐿
),并用 𝑓𝑁𝐿,23𝑛−|𝐶𝑅| +𝑣𝑎𝑙𝑢𝑒(𝐶𝑅)
更新答案。
- 注意到可以 𝑂(1)
转移每一个 𝑓𝐿,𝑘
。具体地说,取 𝑑
为 𝐿
中的任意一个元素,然后分类讨论:- 假设最优解中 𝑑
不在团中,则从 𝑓𝐿∖{𝑑},𝑘
转移而来。 - 假设最优解中 𝑑
在团中,则从 𝑓𝐿∩𝑁(𝑑),𝑘 +𝑣𝑎𝑙𝑢𝑒(𝑑)
转移而来,其中 𝑁(𝑑)
表示 𝑑
的邻居集合。 - 别忘了还要用 𝑓𝐿,𝑘+1
来更新 𝑓𝐿,𝑘
。
这个解法会超时。尝试优化:
- 平分点集时均匀随机地划分。这样的话,最优解的点集 𝐶𝑟𝑒𝑠
以可观的概率也被恰好平分(即 |𝐶𝑟𝑒𝑠 ∩𝑉𝐿| =|𝐶𝑟𝑒𝑠 ∩𝑉𝑅|
)。- 当然,|𝐶𝑟𝑒𝑠|
可能是奇数。简单起见,这里假设它是偶数;奇数的情况对解法没有本质改变。 - 实验发现,随机尝试约 20 次就能以很大概率有至少一次满足该性质。也就是说,如果我们的算法依赖于「𝐶𝑟𝑒𝑠
被平分」这一性质,则将算法重复执行 20 次取最优,同样也能保证以很大概率得到正确答案。
- 有了这一性质,我们就可以直接钦定左侧团 𝐿
、右侧团 𝐶𝑅
的大小都 ≥𝑛3
。这会对复杂度带来两处改进:- 𝑓
可以省掉记录大小的维度。 - 因为只需考虑大小 ≥𝑛3
的团,所以需要考虑的左侧团 𝐿
和 右侧团 𝐶𝑅
的数量也大大减少至约 1.8 ⋅106
。
- 现在的瓶颈变成了求单侧的某一子集的权值和,因为这需要 𝑂(2|𝑉𝐿| +2|𝑉𝑅|)
的预处理。- 解决方案:在 𝑉𝐿,𝑉𝑅
内部再次折半;当查询一个子集的权值和时,将这个子集分成左右两半查询,再把答案相加。
- 这样即可通过本题。
回顾:一个随机的集合有着「在划分出的两半的数量差距不会太悬殊」这一性质,而我们通过随机划分获取了这个性质。
随机化用于哈希
简要题意
维护一棵动态变化的树,和一个动态变化的结点二元组集合。你需要支持:
- 删边、加边。保证得到的还是一棵树。
- 加入/删除某个结点二元组。
- 给定一条边 𝑒
,判断是否对于集合中的每个结点二元组 (𝑠,𝑡)
,𝑒
都在 𝑠,𝑡
间的简单路径上。
对图中的每条边 𝑒
,我们定义集合 𝑆𝑒
表示经过该边的关键路径(即题中的 (𝑎,𝑏)
)集合。考虑对每条边动态维护集合 𝑆𝑒
的哈希值,这样就能轻松判定 𝑆𝑒
是否等于全集(即 𝑒
是否是「必经之路」)。
哈希的方式是,对每个 (𝑎,𝑏)
赋予 264
以内的随机非负整数 𝐻(𝑎,𝑏)
,然后一个集合的哈希值就是其中元素的 𝐻
值的异或和。
这样的话,任何一个固定的集合的哈希值一定服从 𝑅 :={0,1,⋯,264−1}
上的均匀分布(换句话说,哈希值的取值范围为 𝑅
,且取每一个值的概率相等)。这是因为:
- 单个 𝐻(𝑎,𝑏)
显然服从均匀分布。 - 两个独立且服从 𝑅
上的均匀分布的随机变量的异或和,一定也服从 𝑅
上的均匀分布。自证不难。
从而该算法的正确率是有保障的。
至于如何维护这个哈希值,使用 LCT 即可。
本题的大致解法:
- 可以证明 𝑆(𝑁)
服从一个关于 𝑁
的 𝑂(𝐾)
阶线性递推式。 - 用 BM 算法求出该递推式。
- 借助递推式,用凯莱哈密顿定理计算出 𝑆(𝑁)
。
这里仅关注第二部分,即如何求一个矩阵序列的递推式。所以我们只需考虑下述问题:
问题
给定一个矩阵序列,该序列在模 𝑃 :=998244353
意义下服从一个齐次线性递推式(递推式中的数乘和加法运算定义为矩阵的数乘和加法),求出最短递推式。
如果一系列矩阵服从一个递推式 𝐹
,那么它的每一位也一定服从 𝐹
。然而,如果对某一位求出最短递推式 𝐹′
,则 𝐹′
可能会比 𝐹
更短,从而产生问题。
解决方案:给矩阵的每一位 (𝑖,𝑗)
赋予一个 <𝑃
的随机权值 𝑥𝑖,𝑗
,然后对于序列中每个矩阵计算其所有位的加权和模 𝑃
的结果,再把每个矩阵算出的这个数连成一个数列,最后我们对所得数列运行 BM 算法。
错误率分析:
- 假设上述做法求得了不同于 𝐹
(且显然也不长于 𝐹
)的 𝑙
阶递推式 𝐹′
。 - 因为矩阵序列不服从 𝐹′
,所以一定存在矩阵中的某个位置 (𝑖,𝑗)
,满足该位置对应的数列 𝑆𝑖,𝑗
在某个 𝑁
处不服从 𝐹′
。也就是说:
𝑆(𝑁)𝑖,𝑗−𝐹′1𝑆(𝑁−1)𝑖,𝑗−⋯−𝐹′𝑙𝑆(𝑁−𝑙)𝑖,𝑗≢0(mod𝑃)
- 假设 (𝑖,𝑗)
是唯一的不服从的位置,则一定有:
𝑇𝑖,𝑗:=(𝑥𝑖,𝑗⋅(𝑆(𝑁)𝑖,𝑗−𝐹′1𝑆(𝑁−1)𝑖,𝑗−⋯−𝐹′𝑙𝑆(𝑁−𝑙)𝑖,𝑗)mod𝑃)=0
- 显然这仅当 𝑥𝑖,𝑗 =0
时才成立,概率 𝑃−1
。 - 如果有多个不服从的位置呢?
- 对每个这样的位置 (𝑖,𝑗)
,易证 𝑇𝑖,𝑗
服从 𝑅 :={0,1,⋯,𝑃 −1}
上的均匀分布。 - 若干个互相独立的、服从 𝑅
上的均匀分布的随机变量,它们在模意义下的和,依然服从 𝑅
上的均匀分布。自证不难。 - 从而这种情况下的错误率也是 𝑃−1
。
简要题意
给定两张边权为小写字母的有向图 𝐺0,𝐺1
,你要对这两张图分别算出「所有路径对应的字符串构成的多重集」(可能是无穷集),并判断这两个多重集是否相等。如果不相等,你要给出一个最短的串,满足它在两个多重集中的出现次数不相等。
令 𝑓𝐾,𝑖,𝑗
表示图 𝐺𝐾
中从点 𝑖
开始的所有长为 𝑗
的路径,这些路径对应的所有字符串构成的多重集的哈希值。按照 𝑗
升序考虑每个状态,转移时枚举 𝑖
的出边并钦定该边为路径上的第一条边。
要判断是否存在长度 =𝐿
的坏串,只需把 {𝑓0,∗,𝐿}
和 {𝑓1,∗,𝐿}
各自「整合」起来再比较即可(通配符 *
这里表示每一个结点,例如 {𝑓0,∗,𝐿}
表示全体 𝑓0,𝑖,𝐿
构成的集合,其中 𝑖
取遍所有结点)。官方题解中证明了最短坏串(如果存在的话)长度一定不超过 𝑛1 +𝑛2
,所以这个解法的复杂度是可靠的。
接下来考虑具体的哈希方式。注意到常规的哈希方法——即把串 𝑎1𝑎2⋯𝑎𝑘
映射到 (𝑎1 +𝑃𝑎2 +𝑃2𝑎3 +⋯ +𝑃𝑘−1𝑎𝑘)mod𝑄
上、再把多重集的哈希值定为其中元素的哈希值之和模 𝑄
——在这里是行不通的。一个反例是,集合 {"ab","cd"}
与集合 {"cb","ad"}
的哈希值是一样的,不论 𝑃,𝑄
如何取值。
上述做法的问题在于,一个串的哈希值是一个和式,从而其中的每一项可以拆出来并重组。为避免这一问题,我们考虑把哈希值改为一个连乘式。此外,乘法交换律会使得不同的位不可区分,为避免这一点我们要为不同的位赋予不同的权值。
对每一个二元组 (𝑐,𝑗)
(其中 𝑐
为字符,𝑗
为整数表示 𝑐
在某个串中的第几位)我们都预先生成一个随机数 𝑥𝑐,𝑗
。然后我们把串 𝑎1𝑎2⋯𝑎𝑘
映射到 𝑥𝑎1,1𝑥𝑎2,2⋯𝑥𝑎𝑘,𝑘mod𝑄
上(其中 𝑄
为 随机选取 的质数)、再把多重集的哈希值定为其中元素的哈希值之和模 𝑄
。接下来分析它的错误率。
(*)Schwartz–Zippel 引理
令 𝑓 ∈𝐹[𝑧1,⋯,𝑧𝑘]
为域 𝐹
上的 𝑘
元 𝑑
次非零多项式,令 𝑆
为 𝐹
的有限子集,则至多有 𝑑 ⋅|𝑆|𝑘−1
组 (𝑧1,⋯,𝑧𝑘) ∈𝑆𝑘
满足 𝑓(𝑧1,⋯,𝑧𝑘) =0
。
如果你不知道域是什么
你只需记得这两样东西都是域:
- 模质数的剩余系,以及其上的各种运算。
- 实数集,以及其上的各种运算。
推论:若 𝑧1,⋯,𝑧𝑘
都在 𝑆
中等概率独立随机选取,则 Pr[𝑓(𝑧1,⋯,𝑧𝑘) =0] ≤𝑑|𝑆|
。
记 𝐹
为模 𝑄
的剩余系所对应的域,则对于一个 𝐿 ≤𝑛1 +𝑛2
,∑𝑖𝑓0,𝑖,𝐿
和 ∑𝑖𝑓1,𝑖,𝐿
就分别对应着一个 𝐹
上关于变元集合 {𝑥∗,∗}
的 𝐿
次多元多项式,不妨将这两个多项式记为 𝑃0,𝑃1
。
假如两个不同的字符串多重集的哈希值相同,则有两种可能:
- 𝑃0 ≡𝑃1(mod𝑄)
,即 𝑃0,𝑃1
的每一项系数在模 𝑄
意义下都对应相等。 - 𝑃0 ≢𝑃1(mod𝑄),𝑃0(𝑥∗,∗) ≡𝑃1(𝑥∗,∗)(mod𝑄)
,即 𝑃0,𝑃1
虽然不恒等,但我们选取的这一组 {𝑥∗,∗}
恰好使得它们在此处的点值相等。
分析前者发生的概率:
- 观察:对于任意的 𝐴 ≠𝐵;𝐴,𝐵 ≤𝑁
和随机选取的质数 𝑄 ≤𝑄max
,一定有:
Pr[𝐴≡𝐵(mod𝑄)]=𝑂(log𝑁log𝑄𝑚𝑎𝑥𝑄𝑚𝑎𝑥)![\mathrm{Pr}\big[A\equiv B\pmod {Q}\big]=O\Big(\dfrac{\log N \log Q_{max}}{Q_{max}}\Big)](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- 这是因为:使 𝐴 ≡𝐵
成立的 𝑄
一定满足 𝑄∣(𝐴 −𝐵)
,这样的 𝑄
有 𝜔(𝐴 −𝐵) ≤log2𝑁
个;而由质数定理,𝑄max
以内不同的质数又有 Θ(𝑄maxlog𝑄max)
个。将两者相除即可得到上式。 - 在上述观察中取 𝐴,𝐵
(满足 𝐴 ≠𝐵
)为某一特定项在 𝑃0,𝑃1
中的系数(也就等于该项对应的串在 𝐺0,𝐺1
中的出现次数),则易见 𝐴,𝐵 ≤(𝑚1 +𝑚2)𝐿
,得到:
Pr[𝐴≡𝐵(mod𝑄)]=𝑂(𝐿log(𝑚1+𝑚2)log𝑄𝑚𝑎𝑥𝑄𝑚𝑎𝑥)![\mathrm{Pr}\big[A\equiv B\pmod {Q}\big]=O\Big(\dfrac{L\log (m_1+m_2) \log Q_{max}}{Q_{max}}\Big)](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- 所以取 𝑄max ≈1012
就绰绰有余。如果机器无法支持这么大的整数运算,可以用双哈希代替。
分析后者发生的概率:
- 在 Schwartz–Zippel 引理中:
- 取域 𝐹
为模 𝑄
的剩余系对应的域 - 取 𝑓(𝑥∗,∗) =𝑃0(𝑥∗,∗) −𝑃1(𝑥∗,∗)
为 𝐿
次非零多项式 - 取 𝑆 =𝐹

- 得到:所求概率 ≤𝐿𝑄
。
注意到我们需要对每个 𝐿
都能保证正确性,所以要想保证严谨的话还需用 Union Bound(见后文)说明一下。
实践上我们不必随机选取模数,因为——比如说——用自己的生日做模数的话,实际上已经相当于随机数了。
例:(*)子矩阵不同元素个数
问题
给定 𝑛 ×𝑚
的矩阵,𝑞
次询问一个连续子矩阵中不同元素的个数,要求在线算法。
允许 𝜖
的相对误差和 𝛿
的错误率,换句话说,你要对至少 (1 −𝛿)𝑞
个询问给出离正确答案相对误差不超过 𝜖
的回答。
𝑛 ⋅𝑚 ≤2 ⋅105;𝑞 ≤106;𝜖 =0.5,𝛿 =0.2
引理:令 𝑋1⋯𝑘
为互相独立的随机变量,且取值在 [0,1]
中均匀分布,则 E[min𝑖𝑋𝑖] =1𝑘+1
。
- 证明:考虑一个单位圆,其上分布着 相对位置 均匀随机的 𝑘 +1
个点,分别在位置 0,𝑋1,𝑋2,⋯,𝑋𝑘
处。那么 min𝑖𝑋𝑖
就等于 𝑘 +1
段空隙中特定的一段的长度。而因为这些空隙之间是「对称」的,所以其中任何一段特定空隙的期望长度都是 1𝑘+1
。
我们取 𝑘
为不同元素的个数,并借助上述引理来从 min𝑖𝑋𝑖
反推得到 𝑘
。
考虑采用某个哈希函数,将矩阵中每个元素都均匀、独立地随机映射到 [0,1]
中的实数上去,且相等的元素会映射到相等的实数。这样的话,一个子矩阵中的所有元素对应的那些实数,在去重后就恰好是先前的集合 {𝑋1,⋯,𝑋𝑘}
的一个实例,其中 𝑘
等于子矩阵中不同元素的个数。
于是我们得到了算法:
- 给矩阵中元素赋 [0,1]
中的哈希值。为保证随机性,哈希函数可以直接用 map
和随机数生成器实现,即每遇到一个新的未出现过的值就给它随机一个哈希值。 - 回答询问时设法求出子矩阵中哈希值的最小值 𝑀
,并输出 1𝑀 −1
。
然而,这个算法并不能令人满意。它的输出值的期望是 E[1min𝑖𝑋𝑖 −1]
,但事实上这个值并不等于 1E[min𝑖𝑋𝑖] −1 =𝑘
,而(可以证明)等于 ∞
。
也就是说,我们不能直接把 min𝑖𝑋𝑖
的单次取值放在分母上,而要先算得它的期望,再把期望值放在分母上。
怎么算期望值?多次随机取平均。
我们用 𝐶
组不同的哈希函数分别执行前述过程,回答询问时计算出 𝐶
个不同的 𝑀
值,并算出其平均数 ―――𝑀
,然后输出 (―――𝑀)−1 −1
。
实验发现取 𝐶 ≈80
即可满足要求。严格证明十分繁琐,在此略去。
最后,怎么求子矩阵最小值?用二维 S-T 表即可,预处理 𝑂(𝑛𝑚log𝑛log𝑚)
,回答询问 𝑂(1)
。
随机化在算法中的其他应用
随机化的其他作用还包括:
- 防止被造数据者用针对性数据卡掉。例如在搜索时随机打乱邻居的顺序。
- 保证算法过程中进行的「操作」具有(某种意义上的)均匀性。例如 模拟退火 算法。
在这些场景下,随机化常常(但并不总是)与乱搞、骗分等做法挂钩。
本题的标准算法是网络流,但这里我们采取这样的乱搞做法:
- 每次随机一个位置,把这个位置取反,判断大小并更新答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | #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';
}
|
例:(*)随机堆
可并堆最常用的写法应该是左偏树了,通过维护树高让树左偏来保证合并的复杂度。然而维护树高有点麻烦,我们希望尽量避开。
那么可以考虑使用随机堆,即不按照树高来交换儿子,而是随机交换。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | 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
函数的参数)都成立。下证。
期望复杂度的证明
将证,对于任意的堆 𝐴
,从根节点开始每次随机选左或者右走下去(直到无路可走),路径长度(即路径上的结点数)的期望值 ℎ(𝐴) ≤log2(|𝐴| +1)
。
- 注意到在前述过程中合并堆 𝐴,𝐵
的期望复杂度是 𝑂(ℎ(𝐴) +ℎ(𝐵))
的,所以上述结论可以保证随机堆的期望复杂度。
证明采用数学归纳。边界情况是 𝐴
为空图,此时显然。下设 𝐴
非空。
假设 𝐴
的两个子树分别为 𝐿,𝑅
,则:
ℎ(𝐴)=1+ℎ(𝐿)+ℎ(𝑅)2≤1+log2(|𝐿|+1)+log2(|𝑅|+1)2=log22√(|𝐿|+1)(|𝑅|+1)≤log22((|𝐿|+1)+(|𝑅|+1))2=log2(|𝐴|+1)
证毕。
与随机性有关的证明技巧
以下列举几个比较有用的技巧。
自然,这寥寥几项不可能就是全部;如果你了解某种没有列出的技巧,那么欢迎补充。
概率上界的分析
详见 概率不等式 页面。
除了上述页面中提到的各种不等式外,推导过程中还经常会用到以下结论:
自然常数的使用:(1 −1𝑛)𝑛 ≤1e,∀𝑛 ≥1
- 左式关于 𝑛 ≥1
单调递增且在 +∞
处的极限是 1e
,因此有这个结论。 - 这告诉我们,如果 𝑛
个互相独立的事件,每个的发生概率为 1 −1𝑛
,则它们全部发生的概率至多为 1e
。
「耦合」思想
「耦合」思想常用于同时处理超过一个有随机性的对象,或者同时处理随机的对象和确定性的对象。
引子:随机图的连通性
问题
对于 𝑛 ∈𝐍∗;𝑝,𝑞 ∈[0,1]
且 𝑞 ≤𝑝
,求证:随机图 𝐺1(𝑛,𝑝)
的连通分量个数的期望值不超过随机图 𝐺2(𝑛,𝑞)
的连通分量个数的期望值。这里 𝐺(𝑛,𝛼)
表示一张 𝑛
个结点的简单无向图 𝐺
,其中 𝑛(𝑛−1)2
条可能的边中的每一条都有 𝛼
的概率出现,且这些概率互相独立。
这个结论看起来再自然不过,但严格证明却并不那么容易。
证明思路
我们假想这两张图分别使用了一个 01 随机数生成器来获知每条边存在与否,其中 𝐺1
的生成器 𝑇1
每次以 𝑝
的概率输出 1,𝐺2
的生成器 𝑇2
每次以 𝑞
的概率输出 1。这样,要构造一张图,就只需把对应的生成器运行 𝑛(𝑛−1)2
遍即可。
现在我们把两个生成器合二为一。考虑随机数生成器 𝑇
,每次以 𝑞
的概率输出 0,以 𝑝 −𝑞
的概率输出 1,以 1 −𝑝
的概率输出 2。如果我们将这个 𝑇
运行 𝑛(𝑛−1)2
遍,就能同时构造出 𝐺1
和 𝐺2
。具体地说,如果输出是 0,则认为 𝐺1
和 𝐺2
中都没有当前考虑的边;如果输出是 1,则认为只有 𝐺1
中有当前考虑的边;如果输出是 2,则认为 𝐺1
和 𝐺2
中都有当前考虑的边。
容易验证,这样生成的 𝐺1
和 𝐺2
符合其定义,而且在每个实例中,𝐺2
的边集都是 𝐺1
边集的子集。因此在每个实例中,𝐺2
的连通分量个数都不小于 𝐺1
的连通分量个数;那么期望值自然也满足同样的大小关系。
这一段证明中用到的思想被称为「耦合」,可以从字面意思来理解这种思想。本例中它体现为把两个本来独立的随机过程合二为一。
简要题意
有若干个物品,每个物品有一个价格 𝑐𝑖
。你想要获得所有物品,为此你可以任意地进行两种操作:
- 选择一个未拥有的物品 𝑖
,花 𝑐𝑖
块钱买下来。 - 花 𝑥
块钱从所有物品(包括已经拥有的)中等概率随机抽取一个。如果尚未拥有该物品,则直接获得它;否则一无所获,但是会返还 𝑥2
块钱。𝑥
为输入的常数。
问最优策略下的期望花费。
观察:如果选择抽物品,就一定会一直抽直到获得新物品为止。
- 理由:如果抽一次没有获得新物品,则新的局面和抽物品之前的局面一模一样,所以如果旧局面的最优行动是「抽一发」,则新局面的最优行动一定也是「再抽一发」。
我们可以计算出 𝑓𝑘
表示:如果当前已经拥有 𝑘
个不同物品,则期望要花多少钱才能抽到新物品。根据刚才的观察,我们可以直接把 𝑓𝑘
当作一个固定的代价,即转化为「每次花 𝑓𝑘
块钱随机获得一个新物品」。
期望代价的计算
显然 𝑓𝑘 =𝑥2 ⋅(𝑅 −1) +𝑥
,其中 𝑅
表示要得到新物品期望的抽取次数。
引理:如果一枚硬币有 𝑝
的概率掷出正面,则首次掷出正面所需的期望次数为 1𝑝
。
- 感性理解:1𝑝 ⋅𝑝 =1
,所以扔这么多次期望得到 1 次正面,看起来就比较对。 - 这种感性理解可以通过 大数定律 严谨化,即考虑 𝑛 →∞
次「不断抛硬币直到得到正面」的实验。推导细节略。 - 另一种可行的证法是,直接把期望的定义带进去暴算。推导细节略。
显然抽一次得到新物品的概率是 𝑛−𝑘𝑛
,那么 𝑅 =𝑛𝑛−𝑘
。
结论:最优策略一定是先抽若干次,再买掉所有没抽到的物品。
这个结论符合直觉,因为 𝑓𝑘
是关于 𝑘
递增的,早抽似乎确实比晚抽看起来好一点。
证明
先考虑证明一个特殊情况。将证:
- 随机过程 𝐴
:先买物品 𝑥
,然后不断抽直到得到所有物品 - ……一定不优于……
- 随机过程 𝐵
:不断抽直到得到 𝑥
以外的所有物品,然后如果还没有 𝑥
则买下来
考虑让随机过程 𝐴
和随机过程 𝐵
使用同一个随机数生成器。即,𝐴
的第一次抽取和 𝐵
的第一次抽取会抽到同一个元素,第二次、第三次……也是一样。
显然,此时 𝐴
和 𝐵
抽取的次数必定相等。对于一个被 𝐴
抽到的物品 𝑦 ≠𝑥
,观察到:
- 𝐴
中抽到 𝑦
时已经持有的物品数,一定大于等于 𝐵
中抽到 𝑦
时已经持有的物品数。
因此 𝐵
的单次抽取代价不高于 𝐴
的单次抽取代价,进而抽取的总代价也不高于 𝐴
。
显然 𝐵
的购买代价同样不高于 𝐴
。综上,𝐵
一定不劣于 𝐴
。
然后可以通过数学归纳把这一结论推广到一般情况。具体地说,每次我们找到当前策略中的最后一次购买,然后根据上述结论,把这一次购买移到最后一定不劣。细节略。
基于这个结论,我们再次等价地转化问题:把「选一个物品并支付对应价格购买」的操作,改成「随机选一个未拥有的物品并支付对应价格购买」。等价性的理由是,既然购买只是用来扫尾的,那选到哪个都无所谓。
现在我们发现,「抽取」和「购买」,实质上已经变成了相同的操作,区别仅在于付出的价格不同。选择购买还是抽取,对于获得物品的顺序毫无影响,而且每种获得物品的顺序都是等可能的。
观察:在某一时刻,我们应当选择买,当且仅当下一次抽取的代价(由已经抽到的物品数确定)大于剩余物品的平均价格(等于的话则任意)。
- 可以证明,随着时间的推移,抽取代价的增速一定不低于剩余物品均价的增速。这说明从抽到买的「临界点」只有一个,进一步验证了先前结论。
最后,我们枚举所有可能的局面(即已经拥有的元素集合),算出这种局面出现的概率(已有元素的排列方案数除以总方案数),乘上当前局面最优决策的代价(由拥有元素个数和剩余物品总价确定),再加起来即可。这个过程可以用背包式的 DP 优化,即可通过本题。
回顾:可以看到,耦合的技巧在本题中使用了两次。第一次是在证明过程中,令两个随机过程使用同一个随机源;第二次是把购买转化成随机购买(即引入随机源),从而使得购买和抽取这两种操作实质上「耦合」为同一种操作(即令抽取和购买操作共享一个随机源)。
参考资料
本页面最近更新:2025/8/29 18:05:34,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:TianyiQ, Enter-tainer, Tiphereth-A, Ir1d, leoleoasd, ouuan, billchenchina, CCXXXI, HeRaNO, ImpleLee, ksyx, Marcythm, MegaOwIer, partychicken
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用