概率 - 哈希杂谈

简介

我们最常接触的哈希通常是对字符串任意子串的哈希，并且被定义为 $f(l,r)=(\sum_{i=l}^r s_i\times B^{r-i})\bmod P$，其中 $B,P$ 是自选的常数。

然而经过了一系列题目之后，我发现对集合的哈希也是有很多种的，并且有多种的实现方式。

随机权之(异或)和

如果我们不需要对集合进行任何的操作，只需要判断是否相等，通常这种实现是比较好的。

设集合中的元素是 $1\sim n$ 的整数，初始化 $w_1\sim w_n$ 为 $0\sim 2^w-1$ 的数，并定义集合 $S$ 的哈希值 $h(S)=(\sum_{i\in S} w_i)\bmod 2^w$。

若集合 $S\neq T$，不妨设存在 $x\in S$ 且 $x\not\in T$（如果 $S\subseteq T$ 就反过来），那么 $h(S)=h(T)$ 的概率就是下面这个东西的概率：

$$w_x\equiv h(T)-h(S\setminus \{x\})\pmod{2^w}$$

由于式子右侧与 $x$ 完全无关，根据随机初始化的独立性，这个概率就是 $2^{-w}$。

如果整个程序运行过程中，我们需要进行 $n^2$ 次比较，那么碰撞的概率就会有一个 $n^22^{-w}$ 的上界，取 $w=64$ 这个值通常是可以接受的。

通常来讲，上面 $h(S)$ 也可以定义为 $\bigoplus_{i\in S} w_i$，碰撞概率分析同理。

幂之和

如果我们需要对集合进行一个整体加数的操作，赋随机权就没那么好用了。

设集合中的元素是 $1\sim n$ 的整数，并定义集合 $S$ 的哈希值 $h(S)=(\sum_{i\in S} B^i)\bmod P$，这里 $B,P$ 是自选的常数。

这里的概率分析就比较玄学了，在出题人不知道你的 $B,P$ 的情况下，如果你选的 $B$ 为 $P$ 的原根，应当就很难卡掉。

这样定义的好处是，如果你需要整体 $+x$，那么 $h(S)$ 的变化就是 $h(S)\gets (h(S)\times B^x)\bmod P$。

[CF1418G] Three Occurrences

固定一个 $r$，我们考虑有多少的 $l$ 是合法的。

对于恰好三次这个限制，通常可以认为是一个套路，我们通过两个约束保证这一点：

1. 所有数出现次数是 $3$ 的倍数。
2. 所有数出现次数不超过 $3$。

对于第二个约束，满足条件的所有 $l$ 显然是在以 $r$ 为右端点的一个连续区间内的，并且这个区间的边界是可以通过双指针来更新的。

因此我们只需要解决第一个问题。也就是说，我们希望如果一个数出现了三次，那么它对这个集合的哈希值的贡献就为 $0$。

考虑对一个数 $x$ 按照出现次数模 $3$ 分别赋 $w_{x0},w_{x1},w_{x2}$，其中 $w_{x0}+w_{x1}+w_{x2}\equiv 0\pmod {2^w}$ 。

这样一来，只要出现次数是三的倍数，它的贡献就为 $0$。根据上文的概率分析，当出现次数不是 $3$ 的倍数时，哈希值为 $0$ 的概率为 $2^{-w}$。

又因为这里只考虑连续的区间，至多只有 $O(n^2)$ 个区间存在出现次数不为 $3$ 的倍数的元素，也就是隐性进行了 $O(n^2)$ 次比较，根据上文的分析，这个错误概率是比较低的。

[2026 HDU多校 4] Rare Game

$dp$ 的部分比较简单：设 $dp_i$ 表示 $1\sim i$ 的方案数。枚举最后一段，那么转移就是 $dp_i=\sum_{V(j+1,i)=1} dp_j$，其中 $V(j+1,i)=1$ 表示 $a_{j+1}\sim a_i$ 中每一个数的出现次数都是 $4$。

考虑使用哈希处理这个比较难搞的条件。同上，我们也是通过两个约束保证合法性：

1. 所有数出现次数是 $4$ 的倍数。
2. 所有数的出现次数不超过 $4$。

现在和上面那个题目基本上就一样了。

[ABC238G] Cubic?

和上面不一样的是，这里要求的不是每个质因数出现的次数恰好为 $3$，而是 $3$ 的倍数，所以都不需要双指针了。

[HDU8113] 炼金术士的配方

不同于上面的题目，我们不再是需要查询多少个区间的哈希值为 $0$ 的情况，所以之前按照出现次数模 $2$ 的方法加法哈希就不太行了，因为我们无法保证奇数次出现和偶数次出现贡献的东西相等，然后它们加到一起又贡献 $0$。

但是这个东西恰好能用异或的方法表示，这也通常被称为异或哈希。

[JLCPC2025] 另一个回文问题

本质上，本题是询问一个区间内奇数位置构成的多重集是否与偶数位置相同，并且要支持区间加。

只要使用幂之和哈希就可以轻松维护了，并且我们这里可以令位置 $i$ 维护的值是 $(-1)^i B^{a_i}$，这样只需要查询区间和是否为 $0$ 即可。

[ICPC2025 Hong Kong R] DFS Order - Extra Stage

考虑一个 DFS 序对于树结构的限制是什么。

一个显然的必要条件是，如果 $p$ 是一个 DFS 序，那么对任意一个节点 $u$ 的所有后代都必须在 $p$ 中紧连在 $u$ 后面形成一个连续的区间。

这是否充分呢？也就是说，如果对任意一个节点 $u$，它的所有后代都在 $p$ 中紧连在 $u$ 后面形成一个连续的区间，那么 $p$ 就是一个合法的 DFS 序吗？

这是对的。考虑 $u$ 的所有儿子 $s_1,s_2,\dots, s_k$，将它们按照 $p$ 中出现的先后顺序进行 DFS，通过数学归纳法可以证明它能得到 $p$。

给每一个节点 $u$ 开一个哈希表 $h_u$，用 $h_{u,S}$ 表示 $S$ 这个集合在 $p_1\sim p_m$ 中，作为紧连在 $u$ 后面的一个连续区间出现的次数。当且仅当 $h_{u,S}=m$ 时，$S$ 可以作为 $u$ 的后代集合。

由于 $h_{u,S}=m$ 要求 $S$ 在 $p_1$ 中就出现，所以对后续新出现的集合种类，我们可以不把它们加入哈希表，这样空间保持 $O(n^2)$，尽管时间是 $O(mn^2)$。

引用一句我比较喜欢的话，但是忘记出处了：$n=500$ 是一个尴尬的数字，这意味着你的时间复杂度可以是 $O(n^3)$，但是空间复杂度却通常不能是 $O(n^3)$。

这里集合就可以用随机权哈希的方法去处理。

进一步的，如何计数？看到 $n\le 500$，考虑 $O(n^3)$ 的区间 $dp$。

在处理完所有限制后，我们只对 $p_1$ 进行 DP。

设 $f_{l,r}$ 表示区间 $[l,r]$ 能够形成的所有树的种类，如果 $p_{1,l+1}\sim p_{1,r}$ 不是 $p_{1,l}$ 的一个合法后代集合，那么 $f_{l,r}=0$；否则，那么我们枚举第一个子树的管辖范围进行转移：

$$f_{l,r}=\sum_{i=l+1}^r f_{l+1,i}\times g_{i+1, r}$$

其中 $g_{l,r}$ 表示将 $[l,r]$ 划分为若干个区间能够形成的森林的总数。因为枚举第一个子树后，后面的显然是一个森林，所以需要这样设计。

那么它的转移如下：

$$g_{l,r}=\sum_{i=l}^r f_{l,i}\times g_{i+1,r}$$

可以看出，$g_{l,r}$ 是依赖 $f_{l,r}$ 的，但是 $f_{l,r}$ 不会依赖到当前层的 $g_{l,r}$，所以这个转移是不会相互依赖的。