乱搞之神——随机化

· · 算法·理论

引言

UPD#1 25.12.18 修复相关笔误和不严谨的错误，添加 Treap 中的随机化思想

提起随机化，众人第一反应大抵都是抛硬币赌 YES 或 NO。

随机化本身作为一种 "邪门歪道"，被各大普通教育机构的老师摒弃，也并不会在这方面多加讲解。

但是，事实上，随机化的强大，超乎你的想象。

神奇の随机化

随机化，也就是将一段数据打乱，使得其失去原有的部分性质。或者重新使其拥有新的性质。

那所谓的新性质有什么用呢，来几个题目品品：

例 1：反极端数据

比如，你现在需要实现一个排序代码，然而你选择了不稳定的快速排序，这时候有个 CF 来的神秘大黑客，看了一眼你的代码，并构造出了一组有病神秘数据，使得你快排劣化到了 O(n^2)。并成功让你的代码变成了他的 100 分。（哦这可真是一个悲伤的故事我的孩子）

咋办，受着么？

我们可以对需要排序的数组进行随机打乱，使得其中出现这种鬼畜极端数据的概率被打碎降低。

先随机化一次后，快排的时间复杂度就可以使得复杂度的期望达到 O(n\log n)。

当然，以上只是一个例子，考场上建议直接使用 sort 函数。(你在考场上真的会用快排么)

所以我们可以得到随机化的第一个性质：打破原本序列与位置有关性质，使其获得随机性。

例题（仅在一部分应用）：CF2164G 缺点机器（Pointless Machine）

题解：Link

:::info[省流] 容易发现，如果我们想要基于二进制下的毒药问题考虑查询，会被一堆猎奇的形状（满二叉树，链，菊花图等）卡死。

所以我们 shuffle（洗牌，此处指打乱序列）一下原序列后询问，离散化我们询问的点，可以有效打乱妨碍我们回溯查询的图形。 :::

例题 2：ULR#3 T1 储存处无

:::success[题解] 假设你现在已经会了除最后一档以外的所有部分分。

我们会发现，每次的限制在如何确定这个环的特征，我们贪心的考虑：定义这个环中最小的数字为环的特征，然后每次查询时遇到比自己大的就直接跳，但是如果出题人构造一组数据，我们查找环的特征依旧需要 O(n) 的话，时间复杂度还是 O(n^2)，铁过不了。

所以直接随机化。

然后没了。

均摊复杂度 O(n\log n)，因为随机化以后，整个环的特征被打乱，构造的数据就不会卡你了，而且每次找到这个环特征的期望为 O(\log n) 次。

具体证明可参考 Cfz 大佬的题解（也就是官解）。 :::

例 2：性质随机检索

考虑如下题目：

构造一个长度为 n 的序列，要求其中对于任何 1\le l < r \le n，均满足 a_l \oplus a_{l+1} \oplus \dots \oplus a_{r-1} \oplus a_r \neq 0 这一条件。

这题多简单啊，考虑到当一个序列的异或和为 0 时，当且仅当它的前缀异或和 P_{l-1} = P_r，那我只需要构造 n 个不互相同的 P_i 不就可以满足条件了么？

但如果你没想到呢？假如这题前面给你放一个 recall，给你炸傻了，你认为这题是 *3500，没往这上面想。或者说，没想到怎么构造 n 个不互相同的 P_i。

凉拌？退役？不存在的。

我们存储下之前已经构造出来的 P，并从允许的值域中随机抽一个数字 x 出来，如果满足 x \oplus P_{i-1} 不存在这个序列中，不就可以了么。在抽取时间为 O(1) 的情况下，O(n\log n) 是稳过的。

所以我们可以得到随机化的第二个性质：在已知性质但不知道构造方法的情况下，可以选择使用随机数抽一个数字并检查是否符合性质。（最好是那种大部分数字均可以满足的情况）。

例题：[JSOI2016] 反质数序列

:::success[随机化题解] 当一个序列不满足是一个反质数序列时，当且存在有一奇一偶两个数字，它们的和是一个质数。

考虑先随机抽一个数字进去，然后疯狂处理后面的数字（其实相当于 shuffle 一下数组然后慢慢处理），贪心的把每次合法的数字都怼进去。

但可能第一次抽的不优，所以可以多来几次，取最大值。建议使用神秘卡时技巧最大化抽取次数。

复杂度 O(kn^2)，其中 k 为 shuffle 次数。

如果你赛时没有想到二分图的一堆神秘优化，这个是真的可以救命的。 :::

例子 2：【CSP - S2022】星战（蒙特卡洛算法）

:::success[题解] 不讨论”不可以，总司令“

容易发现，如果总的度数为 n，且每个点都存在一个出边的时候是绝佳的时机，其它都不是。

直接动态维护一定超时。

考虑直接统计出度总和，如果出度总和为 n，它就满足了答案的一个充分条件。

考虑如何让这个条件变成充要条件：给每一个点赋一个随机的权值，并统计一个总权值之和 sum：

\sum_{i \in V} w_i \times out_i

其中 w_i 为随机点权，out_i 为出度。

每次修改的时候，通过对出度操作改变这个总和，随后和 sum 比较，如果相同就是 YES，否则就是 NO。

做完了。

这个题目还是比较具有科普性的。这个思想的本质是蒙特卡洛算法：运行的时间是固定的，但是答案有小几率出错。 :::

例 3：均匀离散

考虑以下题目（QOJ14421 Far Away）：

给定一个 n 个点 m 条边的图，q 次查询两个点，判断它们的距离是否超过 20000，如果两个点无法彼此到达，距离视为无限大。

想要全源最短路？不好意思，n \le 10^5。

那咋办？

我们先不考虑连通分量的问题，如果一个连通分量的大小小于 20000，那么这里面点的距离绝对都小于 20000。

所以，我们可以对这个连通分量内随机撒一些关键点，然后对这些点跑单源最短路，获得它到可到达的每一个点的距离，然后每次查询两个分量内的点时，就通过绕一个关键点判断距离是否超过 20000。

为什么使用随机数撒点？因为它均匀（啊对）。它可以保证在绝大多数的情况下，覆盖到满足条件的路径上，进而使得我们在查询时可以通过这些点获得正确的路径。

而且你会发现这题在 QOJ 上被禁用 Hack 了，说明本题做法是倾向于随机化这一类容易被神奇数据卡的算法的

神奇の随机抽取

如果现在，需要你构造一堆神秘的东西，你不会，咋办？

但是，假如你知道了，抽到一个符合这个条件的数的概率极大，就可以用随机抽取处理。

例：质数期望（拉斯维加斯算法）

先放结论：从 1\sim n 中等概率随机抽一个整数出来，这个整数是质数的概率近似为 \frac{1}{\ln n}。

考虑以下问题：

找到一个非质数 n，对其质因数分解后去重，满足其不重质因数的和等于 m-1（m\le 10^9 且 m 是一个奇数）。

直接构造 n 显然不现实，但我们可以简化问题：把 n 分解成两个质数的乘积，然后考虑 p+q+1 = m。

由哥德巴赫猜想（每一个大于 2 的偶数均可以被分割成两个质数的和，已被验证 10^9 内成立）得一定存在两个质数满足其加和为 m-1，但如何找到这两个质数？10^9 完美卡死了所有算法。

所以我们使用神秘的随机数，从 10^9 中随机抽取一个数字，然后取 m-1-p，判断二者是不是质数即可。

最后随机数的思想本质是拉斯维加斯算法：答案永远正确，但是时间无法确定。

时间复杂度 O (能过)。

时间复杂度 O(k\sqrt{m})。

我们期望在 O(\ln n) 次内抽出一个偶数，经测试，在一秒的时限内可以通过此题。（证明 k 的准确期望难度不亚于证明哥德巴赫猜想成立，主包暂时不想拿菲尔兹奖）

当然也可以用更为优秀的素数判断代码优化掉根号。

神奇の哈希

此处不是哈希科普课，暂不科普哈希，默认你会。

哈希这个东西，你学的路径一定是：学哈希，用哈希，（被）卡哈希。

总有那些神奇的出题人，为了防止自己心爱的串串题被神经的哈希算法 [CENSORED] 过去，出题人一定会把自己这辈子知道的模数和基值都卡一遍，就算出题人不整你，也总有那些神人会对着你的代码 Hack，让你变成他的 100 分。

我的教练曾经为了防止被卡，写了一个固定五层哈希上去，本以为高枕无忧，结果比赛结束后就收到了 CF 的被 Hack 提示。

所以如何防止被卡呢，这是一个好问题，在讨论这个之前，我们先看一个例子：

例 1：卡哈希：生日悖论 / Hash Killer II

题意：

原题：一个长度为 n 的字符串，求有多少个长度为 l 的不同字串。

现在给你一段求解该问题的单 Hash 代码，其中模数固定为 10^9+7，但不确定 Base 的值。你需要构造这个字符串使得 Hash 代码发生哈希冲突以给出错误的答案。

看上去是不是一脸无敌：这 Base 都不知道怎么卡？

我们引入一个悖论：

假如一个房间里的人数超过了 23 个，那么这个房间里至少存在两个生日相同的人的概率不低于 50\%。

听上去挺离谱的：对于每个人，不应该是 \frac{22}{365} 的概率存在一个和自己生日相同的人么，这概率显然远远小于 \frac{1}{2}。

但实际上，我们反向考虑一下：23 个人生日互不相同的概率是多少？

对于第二个人而言，他不与第一人生日相同的概率为 \frac{364}{365}，同理，所以最后会发现这个概率为：

P(23) = \frac{364!}{343!\times 365^{23}} \approx 0.4927 1-P(23) \approx 0.5073

很诧异，不是么？

于是，我们可以用同样的方法总结出一个结论：

对于单哈希而言，期望在 \sqrt{Mod} 次内发生哈希冲突。

所以直接随机生成一个长度为 n 的字符串就做完了。

例 2：不被卡：Hash Killer III

首先，你需要知道，Hash Killer III 是一个尚未被解决的 Open Problem，所以你在时间允许的情况下，在 CF 使用 Hash Killer III 的方法是绝对不会被人卡的（否则建议那人提名图灵奖）。

那我们来分析一下 Hash Killer III：

首先，Hash Killer III 依旧采用了随机的 Base，但其却使用了随机的素数模数 Mod1 和 Mod2，成为了一个随机双哈希。

此时会发现，触发生日悖论的条件变得苛刻了，其要求同时在取模两个随机数的情况下发生错误，概率小到了一个可以忽略不计的地步。（顺道膜拜 hzhwcmhf 大神）

此处提及 Hash Killer III 并不是说明生日悖论的错误，而是提及我们说到的随机化的性质一：打乱性质。

随机化使得那些针对性的数据完全失效，但同时也会被随机化卡。双哈希的重复检验使得绝大部分的随机构造都占不到便宜，但却容易被针对性数据卡（缅怀我教练的固定五哈希），而两两结合，就可以使得大部分的卡法失效，变成近乎无解的状态。

我们利用生日悖论简单推演一下双哈希为什么不容易被随机化卡：两个大质数 Mod1\times Mod2 \approx 10^{18}，冲突需要在 \sqrt{10^{18}} = 10^9 时才会大概率发生，但是在大部分情况下，n 最大也才 10^6，很难走这种方式卡掉。

但同样的，无人证明这个玩意是无敌的，只是无人找到那个序列而已。但对于 OI / ACM 而言，已经是足够用的了。

神奇の数据结构

注：因为我是 ds 蒟蒻，所以这里仅讨论随机化思想

想不到吧，数据结构也能用随机化。

什么，您是 ds 大佬？打扰了。

首先，我们引入一个老生常谈的问题：针对一个 BST ，如何使得它无法被劣化成链。

这时候我们肯定不能用随机化把询问序列给 shuffle 了，这样子一定会错。

于是，我们依旧考虑随机化。

我们会发现，一个 BST 退化成链，就是给入的数据太单调了。

那既然数据在权值上是单调的且我们不好动权值，那我们就再加一个随机权值。

考虑对于每一次插入时，都给插入的点赋予一个随机值，保证在处理 BST 的插入时候，这个随机权值符合大根堆 / 小根堆的性质，就可以有效优化退化问题。

本质上还是运用了随机化均匀的特性获取相对离散的值，然后依据这个值控制树的形状。每次查询的期望复杂度为 O(\log n)

后记 / 致谢

写这个也应该算是我的个人学习笔记了。后续会不断补充，丰富内容。

如果有错误，欢迎指出修改。

感谢名单：

参考文献：