哈希方法

序列哈希

即字符串哈希，快速比较两个序列的相等情况。一般来讲我们采用 $b$ 进制方式的哈希，即 $f(s)=\sum_{i=1}^{l}s_i\times b^{l-i}$。

配合二分，字符串哈希可以以 $O(kn\log n)$ 的时间复杂度完成允许失配 $k$ 次的字符串匹配问题。

集合哈希

树哈希

哈希表

例题

刷基础

[CSP-S 2022] 星战

Portal.

要求所有点的出度都是 $1$。其实是要维护一个可重集，对于每一条边，都要将这条边的起点加入集合。只有这个集合恰好为 $1\sim n$ 的集合才是合法的。

因此直接使用集合哈希维护，摧毁和修复节点的操作都是加减法可以完成的。代码。

注意这里只能用 sum Hash，xor Hash 是错误的，比如一个点的出度为 $3$ 也会被视作为合法的。

[AMPPZ 2023] Fibonacci Fusion

Portal.

首先需要取枚举每一个数，不妨枚举那个比较大的数，发现不同的合法的较小的数最多只有两个。因为斐波那契数想要变大，过两项就会翻倍。这样在大数确定时，和不能翻两倍。

我们要找出比这个大数大的斐波那契数，观察通项公式 $f_n=\frac{1}{\sqrt{5}}\left(\left(\frac{(1+\sqrt{5})}{2}\right)^n - \left(\frac{(1-\sqrt{5})}{2}\right)^n\right)$，在 $n$ 足够大时可以直接将后面减的那一项放缩掉，便可以直接解出 $n$（两边取自然对数，一个数的自然对数可以通过它的位数估计），然后对这些斐波那契数求解即可。

高精度计算肯定是不行的，我们直接让所有数在对大质数取模意义下计算即可。笔者的实现为了保险采用了双哈希，但感觉没必要，代码。