一些 trick (6) | 随机化（带权 hash）

· · 算法·理论

例题 1.P3587

给定一个长度为 n 的环，环上每个点有颜色。对于切两刀把它分成两个非空的链的方案，使得每种颜色只在一条链上出现：求方案数和最小的两端链长度之差，保证存在方案。

首先环是诈骗的，本质上那个不包含 $n$ 号点的链就是 $[0,n-1]$ 的一个子区间。一个区间合法，当且仅当每个颜色要么都在它当中出现或者都不在。 考虑给每个点赋一个随机在 $2^{64}$ 以内的权值，使得同种颜色的异或和为 $0$。这样，合法的区间区间异或和一定为 $0$，而不合法的区间只有 $\dfrac{1}{2^{64}}$ 的概率异或和为 $0$，出错率最大可能大约是 $1-(1-\dfrac{1}{2^{64}})^{5\times10^{11}}\approx\dfrac{5\times10^{11}}{2^{64}}$，可以忽略不计。 因此题目转化成了求 $s_0,s_1,s_2,\cdots,s_{n-1}$（$s$ 是权值的前缀异或）中，选出两个同样的数的方案和离 $\dfrac{n}{2}$ 最近的距离。这是简单的。复杂度依实现 $O(n)$ 或 $O(n\log n)$。 例题 2.[P8819](https://www.luogu.com.cn/problem/P8819) 给定一张 $n$ 点 $m$ 边有向图，初始所有边都被激活，要求支持 $q$ 次修改： - 激活/冻结一条边。 - 激活/冻结所有终点为某个特定点的边。 每次修改后询问激活的边生成的子图是否是一个内向基环树。 $n,m,q\le5\times10^5$。 考虑一个弱化的判定。我们考虑检查边数是否是 $n$。这可以通过维护入度实现。但是这并不是充要条件，因为我们无法区分不同的点。 考虑给每个点赋一个随机在 $2^{64}$ 以内的权值，则判定则为所有激活的边起点权值和是否为点权和。对于每个点以其为终点的边，维护其起点的边权和。这是容易的。即使精心构造，一次询问出错率最大也只可能是 $\dfrac{5\times10^5}{2^{64}}$，总出错率最大约为 $\dfrac{2.5\times10^{11}}{2^{64}}$，可以忽略不计。 时间复杂度 $O(n+m+q)$。 例题 3.[CF1830C](https://codeforces.com/problemset/problem/1830/C) 给定一个数 $n$ 和 $k$ 个区间 $\left[\ell_i,r_i\right]\subseteq [1,n]$。 称一个长度为 $n$ 的合法括号序列是好的，当且仅当它的每一个区间 $\left[\ell_i,r_i\right]$ 内的子串都是合法括号序列。 求好的括号序列的数量，答案对 $P=998{,}244{,}353$ 取模。 $n,k\le 3\times10^5$。 根据括号序列前缀和的判定，如果这个括号序列的 $[\ell_1,r_1]$ 和 $[\ell_2,r_2]$ 的子串都是合法括号序列，那么它们的交，并，差（不一定是区间）都是合法的，而且根据合法括号序列删掉一个合法子串也是一个合法括号序列，而且全串也是合法的，因此容易得出一个括号序列是好的的充要条件是“对于每个在区间内出现情况相同的下标，它们组成的子序列是合法括号序列”。如果我们能知道每个下标在区间内出现情况的等价类，容易求出答案。 考虑对于每个区间赋一个随机在 $2^{64}$ 以内的权值，则对于每个区间内的点异或上该权值，那么出现情况相同就转换成了异或值相同。容易差分维护。错误率分析显然。复杂度依实现 $O(n)$ 或 $O(n\log n)$。 已经加入 [一些 trick](https://www.luogu.com.cn/blog/483824/some-tricks)。