Random Hash

JeffZhao · 2025-01-11 18:25:52 · 算法·理论

模型 1：给定一个长度为 n 的序列 a，可以有重复元素，问：

• • 1.$ 当区间 $[l , r]$ 有的数出现了奇数次，但区间异或和为 $0$ 时，答案会出错。根据刚才的结论，出错的概率为 $\dfrac{1}{2^{64}}

模型 2：给定两个集合 A 和 B，问：

• • 2.$ 如何计算错误的概率？考虑消去 $A$ 和 $B$ 公共元素，则 $A$ 和 $B$ 独立，并且在 $0\sim 2^{64} - 1$ 内完全随机。则错误的概率为 $\dfrac{1}{2^{64}}

模型 3：给定一个序列 a，问：

• 1.$ 给每一个出现的数 $x$ 随机赋一个 $0 \sim 2^{64} - 1$ 内的权值 $c_x$，使得 $k$ 个相邻的并且相等的 $c_x$ 异或和为 $0$（注意，它们三个在原序列中不一定相邻），这样，若所有数出现次数都是 $k$ 的倍数，则区间异或和必然为 $0$，错误的概率为 $\dfrac{1}{2^{64}}
• 2.$ 给每一个出现过的数 $x$ 随机赋一个权值 $c_x$，求出这个区间 $c$ 值的和 $\text{sum}$，若 $\text{sum}$ 不是 $k$ 的倍数，输出 `NO`。错误的概率最坏为 $\dfrac{1}{2}$，随机 $30$ 次，错误的概率最坏为 $\dfrac{1}{2^{30}}

P4065 [JXOI2017] 颜色

• 给定一个长度为 n 的整数序列，每一个数都有一个颜色 a_i

• 定义“删除颜色 x” 为把所有的满足 a_i = x 的 a_i 删掉。问有多少种删除颜色的方案，使得最后剩下的数形成原序列的一个子区间。

• 例如，假设 a 初始为 \{1 ,2 ,3 ,2 ,2\}，若删掉颜色 3，则变为 \{1,2\} 和 \{2, 2\}，不是一个子区间；若删掉颜色 1，则变为 \{2,3,3,2\}，是一个子区间。

• 两个方案不同当且仅当至少存在一个颜色 i 只在其中一个方案中被删去。

• 1\leq n \leq 3\times 10^5$，$1\leq a_i \leq n

• 设 [l , r] 为删除后的子区间，则任意一个在区间 [l , r] 的颜色 x，都应该满足：序列中 所有的 颜色 x 只在 区间 [l , r] 出现。

• 考虑给每一个位置 i 赋一个 0\sim 2^{64} - 1 范围内的数 c_i，并且要满足，对于任意一个颜色 x，所有满足 a_i = x 的 c_i 的异或和为 0。

• 而当一个区间 [l , r] 区间异或和为 0，并不能保证区间 [l , r] 是合法的。当一个区间 [l , r] 区间异或和不为 0 时，却 一定 能保证区间 [l , r] 是非法的。

• 因此，我们考虑当区间 [l , r] 异或和为 0 时（即当区间 [l , r] 不合法但区间异或和为 0 时），出错的概率。

• 区间不合法意味着存在一个颜色 x，使得颜色 x 不只是在区间 [l , r] 出现。此时我们认为区间 [l , r] 异或和在 0\sim 2^{64} - 1 中等概率出现，因此判定一个区间是否和合法区间时，出错率为 \dfrac{1}{2^{64}}，正确率为 1 - \dfrac{1}{2^{64}}。

• 设 S_i 表示 c_1 \sim c_i 的异或和。则剩下的任务是统计有多少个区间 [l , r] 使得区间 S_r \oplus S_{l - 1} = 0 即 S_r = S_{l - 1}

• 代码

S2oj #1497 树

• 给定一棵 n 个结点的树，树上每条边有边权

• 给你 q 组询问，每次给定 u 和 v，问 u \rightarrow v 这条路径上的边权是否能重新排列，形成一个回文序列。强制在线。

• 1\leq n \leq 10^6$，$1\leq q \leq 2\times 10^7

• 若一个序列可以形成回文序列，需要满足以下两个条件 之一：

• 给每一种边权 x 随机赋上一个在 0\sim 2^{64} - 1 的值 c_x。

• 设 d_u 表示 1 \sim u 路径上所有 c_x 的异或和。

• 则查询时判定 d_u \oplus d_v 是否等于 0 或者等于某一个在 树的边权 出现过的 c_x 即可。

• 考虑单次查询错误的概率，即当路径上不满足条件 1 和条件 2 时，异或和等于 0 或者某一个 c_x 的概率，最坏为 (n + 1) \times \dfrac{1}{2^{64}}，是一个非常小的数值。

• 代码

CF869E The Untended Antiquity

• 给定一个 n \times m 的网格。

• q$ 次操作，每次给定三个参数 $\text{opt}$，$x_1$，$y_1$，$x_2$，$y_2
• • 若 \text{opt} = 1，表示给以 (x_1,y_1) 为左上角，(x_2 , y_2) 为右下角的矩形围上篱笆。
  • 若 \text{opt} = 2，表示给把以 (x_1,y_1) 为左上角，(x_2 , y_2) 为右下角的矩形的篱笆拆掉（保证这个篱笆存在）
  • 若 \text{opt} = 3，表示查询方格 (x_1 , y_1) 和方格 (x_2 , y_2) 是否连通

• 数据保证任意修建的两个篱笆都不相等，并且对于任意两个篱笆，要么包含，要么完全不相交。

• 1 \leq n, m \leq 2500$，$1 \leq q \leq 10^5

• 考虑如何判定两个方格连通。给每一个篱笆一个编号，设围住 (x_1 , y_1) 的篱笆集合为 S_{x_1 , y_1}，围住 (x_2 , y_2) 的篱笆集合为 S_{x_2 , y_2}。发现若满足 S_{x_1 , y_1} = S_{x_2 , y_2}，则 (x_1 , y_1) 和 (x_2 , y_2) 连通。

• 如何判定两个集合全等？考虑给每一个编号（编号记做 i）的篱笆赋一个 0\sim 2^{64} - 1 的权值 c_i。则只需要判断 S_{x_1 , y_1} 内所有 c_i 的异或和 v_1 是否等于 S_{x_2 , y_2} 内所有 c_i 的异或和 v_2。

• 如何给一个矩形范围内所有的方格的集合 S_{x , y} 都添加上编号 i？使用二维差分 + 二维树状数组即可。

• 代码

ABC 250E Prefix Equality

• 给定两个长度为 n 的数列 a 和 b。

• 有 q 组询问，每次询问给定两个参数 i 和 j，询问 a_1 \sim a_i 排序去重后形成的序列 A，是否等于 b_1 \sim b_j 排序去重后形成的序列 B。

• 1\leq n \leq 2\times 10^5$，$1 \leq q \leq 2\times 10^5

• 考虑模型 2，给每一个在 a 或者 b 出现过的数随机赋一个 0\sim 2^{64} - 1 的权值。

• 维护 a 的异或前缀和 s_1[i] 和 b 的异或前缀和 s_2[i]

• 对于 a[i]，如果存在一个 j < i 使得 a_j = a[i]，则只需令 s_1[i] \leftarrow s_1[i - 1] 即可。否则令 s_1[i] \leftarrow s_1[i - 1] \oplus c[a[i]]

• 最后判定 s_1[i] 和 s_2[j] 是否相等即可。

• 代码

CF1418G Three Occurrences

给定一个长度为 n 的序列 a

问有多少个子区间满足：所有数都 恰好 出现了 3 次。

1 \leq n \leq 5 \times 10^5$，$1 \leq a_i \leq n

• 对于一个区间 [l , r]，若区间 [l , r] 所有数出现次数恰好为 3 当且仅当：

• • 1.$ 所有数出现次数都 $\leq 3

• 枚举右端点 r，考虑统计 1 \sim r 有多少个 l 使得区间 [l , r] 满足条件。

• 对于 1，枚举 r 的同时维护最小的 j，使得当 l 满足 j \leq l \leq r 时，有 [l , r] 所有数出现次数不超过 3。

• 给每一个数 x 随机赋一个 0\sim 2^{64} - 1 内的权值 c_x，使得三个相邻的值相同的 c[a[i]]，c[a[j]]，c[a[k]] 异或和为 0

• 然后求出 c[a[i]] 的前缀异或和 S[i]，即 c[a[1]] \sim c[a[i]] 的异或和。

• 对于一个区间 [l , r]，若满足 S[r] \oplus S[l - 1] = 0，即 S[r] = S[l - 1]，则我们认为区间 [l , r] 所有数的出现次数是 3 的倍数。错误概率为 \dfrac{1}{2^{64}}。

• 那么剩下的任务就是对于一个 r，统计 j \sim r 内有多少 l 使得 S[r] = S[l - 1]，用 std::map 作为桶即可。

• 代码

P8819 [CSP-S 2022] 星战

• 给定一张 n 个点 m 条边的有向图

• 给定 q 个操作，首先给定一个参数 t 表示操作类型：

• • 若 t = 1，表示摧毁一条边 u\rightarrow v，数据保证这条边存在。

  • 若 t = 2，表示摧毁所有指向 u 的边 v \rightarrow u

  • 若 t = 3，表示恢复一条边 u \rightarrow v，数据保证 u \rightarrow v 这条边已经被摧毁。

  • 若 t = 4，表示恢复 最初 所有指向 u 的边 v \rightarrow u

• 每次操作后，请判断当前的图是否是一个内向基环树森林。如果是输出 YES，否则输出 NO。

• 1\leq n \leq 5\times 10^5$，$1 \leq q \leq 5\times 10^5

• 内向基环树森林 \leftrightarrow 所有的点有且仅有一条出边。

• 最直接的想法是给每一个点 i 维护一个 \text{cnt}[i] 表示 i 的出度，每次操作完之后看看所有点的出度是否都是 1。但是对于 t = 2 和 t = 4 就有些棘手了，因为对于所有的 v\rightarrow u，我们需要给所有的 v 执行 \text{cnt}[v] \leftarrow \text{cnt}[v] - 1 或者 \text{cnt}[v] \leftarrow \text{cnt}[v] + 1

• 发现似乎维护每一个点的入度更方便一些。但入度并不能帮助我们判定一个图到底是否是内向基环树森林。

• 考虑把每一条边 u \rightarrow v 的出点 u 放到一个多重集合 S， 然后把 1 \sim n 每一个点放到一个多重集合 T 里。发现如果我们想判定这个图是否是內向基环树森林，我们只需要判定 S 和 T 是否全等。

• 立刻想到模型 2，给每一个点 x 随机赋一个 0\sim 2^{64} - 1 范围内的数 c_x。设 \text{sum} 表示集合 S 的 c_x 的和。若要判定 S 和 T 是否全等，我们只需要判定是否 \text{sum} = \displaystyle \sum_{i = 1}^{n} c_i

• 设 s_u 表示所有指向 u 的点 x 的 c_x 之和。设 d_u 表示 最初 指向 u 的点的 x 的 c_x 之和。

• • 若 t = 1，令 \text{sum} \leftarrow \text{sum} - c_u，s_v \leftarrow s_v - c_u

  • 若 t = 2，令 \text{sum} \leftarrow \text{sum} - s_u，s_u = 0

  • 若 t = 3，令 \text{sum} \leftarrow \text{sum} + c_u，s_u \leftarrow s_v + c_u

  • 若 t = 4，令 \text{sum} \leftarrow \text{sum} + d_u - s_u

• 代码

CF1746F Kazaee

给定一个整数序列 a，有 q 次操作，每次操作有两种类型：

• 把某一个位置 i 的值修改成 x，即 a_i \leftarrow x

• 给定 l，r，k 三个参数，每次询问是否区间 [l , r] 的数出现次数都是 k 的倍数。

• 1 \leq n \leq 3 \times 10^5$，$1 \leq q \leq 3\times 10^5

• 给每一个出现过的值 x 随机赋一个在 0 \sim 2^{31} - 1 的值 c_x。如果所有数在区间 [l , r] 出现次数都为 k 的倍数，则区间 [l , r] 内所有数的和一定为 k 的倍数！

• 当区间 [l , r] 存在一些数出现次数不是 k 的倍数，而区间和是 k 的倍数时，答案会出错。感性证明：肯定是 k 越小，冲突的概率越大，则 k 最小可以取 2（因为 k = 1 肯定输出 YES）；肯定是当区间内只有一种数的时候随机性更强一些。

• 则设这个数为 x，以及其出现的次数 \text{cnt}，则需要计算 \text{cnt} \times c_x \bmod k = 0 的概率。令 \text{cnt} \leftarrow \text{cnt} \bmod k，再令 \text{cnt} \leftarrow \dfrac{\text{cnt}}{\gcd(\text{cnt} , k)}，k \leftarrow \dfrac{k}{\gcd(\text{cnt} , k)}，最终使得 k 和 \text{cnt} 互质。则需要满足 c_x \bmod \dfrac{k}{\gcd(\text{cnt} , k)} = 0，而由于 \text{cnt} < k，则 \dfrac{k}{\gcd(\text{cnt} , k)} \geq 2。由于 c_x 纯随机，所以错误的概率最坏是 \dfrac{1}{2}

• 重复上述操作 30 次：给所有值随机赋值，用树状数组或者线段树维护区间 c 值的和，只要这 30 次内有 1 次发现区间和不是 k 的倍数，就可以直接判定本次询问为 NO。

• 错误的概率为区间不满足每一个数出现次数都是 k 的倍数，但是这 30 次每次区间和都是 k 的倍数，概率最坏为 (\dfrac{1}{2})^{30} = \dfrac{1}{2^{30}}，可以接受。

• 注意每次随机时，不应该直接把 c 数组设置成 unsigned int 或者 unsigned long long。因为树状数组单点修改时，有可能会加上一个负数，而这两个数据类型是不能表示负数，会自动对 2^{32} 或者 2^{64} 取模，而取模之后 \bmod k 就失去了意义。

• 代码

[ABC367F] Rearrange Query

• 给定一个长度为 n 的正整数序列 a 和 b

• 有 q 组询问，每次询问给定两个参数 l 和 r，问 a_l \sim a_r 重新排列后是否能等于 b_l \sim b_r。

• 1 \leq n \leq 2\times 10^5$，$1\leq q \leq 2\times 10^5$，$1\leq a_i,b_i \leq n

• 把 a_l \sim a_r 看做集合 A，把 b_l \sim b_r 看做集合 B，则只需判定集合 A 和 集合 B 是否相等即可。

• 由于 A 和 B 内部可能有重复元素出现，所以用 和哈希 Sum-Hash 而不是异或哈希 Xor-Hash

• 给每一个在序列 A 或者 B 出现的数 x 随机赋一个 0 \sim 2^{64} - 1 的数值 c_x

• 则维护 a 序列 c_{a_1} \sim c_{a_i} 的和 s_1[i]，以及 b 序列 c_{b_1} \sim c_{b_i} 的和 s_2[i]。查询时，判断 s_1[r] - s_1[l - 1] 和 s_2[r] - s_2[l - 1] 是否相等即可。

完结撒花！欢迎勘误！