哈希：从入门到入土

本题单不断更新。 同一版块内大致按难度排序。 ------------ 如何辨别哈希题？大概就通过一句话： - 当需要用 $\Theta(1)$ 的时间快速比较两个 $\Theta(n)$ 的东西时。 应该来说，对大部分题目都生效。 ### 序列哈希 序列哈希即最普通的字符串哈希；即用于快速比较两个序列 $\{a_n\}$ 和 $\{b_n\}$ 是否有 $\forall 1\le i\le n$ 满足 $a_i=b_i$ 时。 一般而言，通常使用哈希函数为 $h(\{a_n\})=\sum\limits_{i=1} a_i\times base^i$，即最经典的多项式哈希。 P3370：毫无技巧的字符串哈希。 ARC172C：哈希的简单应用。 P3375：不会 KMP 怎么办？哈希启动！ P4824：不会 KMP 怎么办？哈希再次启动！ P4407：简单哈希，但是重复情况需要讨论。 P3763：哈希做法和 SA 做法原理相同，但是好写很多。 P3449：@[lzyqwq](/user/539211) 巨佬推荐的哈希好题，可以看看他的题解。 ### 集合哈希 集合与序列的不同点在于，集合是无序的，也就是说，序列要求每个位置一一相等，而集合只需要对应的元素出现次数相等即可。 此时的哈希函数一般可以表示成如下形式：$h(\{a_n\})=\sum\limits_{i=1}^n h'(a_x)$。 特殊地，常用的哈希函数有两种： - 随机权值哈希，即我们给每个元素 $x$ 赋一个随机数 $r_x$，然后 $h(\{a_n\})=\sum\limits_{i=1}^n r_{a_i}$。 - 将原集合映射成一个 $01$ 序列，即若该元素 $x$ 出现在集合中，第 $x$ 位置为 $1$，否则为 $0$，然后对得到的 $01$ 序列进行字符串哈希即可；如果原集合是可重集，那么对应的，原来 $01$ 的每个位置上保存每个元素的出现次数即可，也就是哈希函数 $h(\{a_n\})=\sum\limits_{i=1}^n base^{a_i}$。 CF1175F：板题，复杂度均摊分析。 CF1418G：带一点技巧性的集合哈希，尺取时动态维护哈希值变化。 P8819：网红题，先分析性质然后动态维护一下哈希值（其实也可以理解成序列哈希）。 ### 树哈希 树上的哈希一般通过子树转移而来，形式灵活多变。 P5043：树同构哈希。 CF1794E：对距离进行集合哈希，通过换根 dp 巧妙转移。 ### 数据结构维护哈希值 如果说，遇到下面这一道题目，要求做到 $\Theta(q\log n)$，该如何应对？ > 给定一个序列 $\{a_n\}$ 和 $\{b_n\}$，有三种操作： > > ``1 p x``，令 $a_p\gets x$。 > > ``2 p x``，令 $b_p\gets x$。 > > ``3 l r l1 r1``，询问 $a_{l\sim r}$ 和 $b_{l1\sim r1}$ 是否相等。 每次修改时直接暴力更新整个序列的哈希值复杂度是 $\Theta(nq)$ 的，但是我们发现，其实本质上哈希值只有对应的第 $p$ 位发生了改变，所以其实相当于对哈希值的单点修、区间查，线段树即可。 P3792：应该算是板题，动态修改，线段树维护。 CF1746F：也是板题。 P5278：P3792 的加强版，~~lxl 上课的例题，我直接哈希，lxl 表示震惊~~，正解做法实现起来比较麻烦，但是通过集合哈希的第二种哈希方法可以快速计算一个等差序列的哈希值（参考第五篇题解）。 CF1771F：xor hash，状态有区间和值域两维，主席树维护。 P2757：特别巧妙的题，然后应该是线段树维护哈希板子。 P4036：有插入操作，平衡树维护哈希。 P5537：非常聪明的题，看似与哈希毫无关系，实则非常巧妙。