哈希（字符串哈希 & 和哈希 & 树同构） 笔记

一、字符串哈希

这个比较简单，直接把字符串看成一个若干进制数，按照二进制转十进制的方法转成十进制即可。但会发现肯定爆完了，所以找个合适的模数取模。

如 $\mathtt{\text{abd}}$，如果将其看成 $27$ 进制（其中 $\mathtt{\text{a}}=1,\mathtt{\text{b}}=2,\dots$），最左边是第 $0$ 位，对 $1331$ 取模：

$$\mathtt{\text{abd}}=(\mathtt{\text{a}}\times {27}^0+\mathtt{\text{b}}\times {27}^1+\mathtt{\text{d}}\times {27}^2)mod1331=2971mod1331=309$$

直接来到强度题：

1. P2757 [国家集训队] 等差子序列

找长度 $\ge 3$ 的等差子序列，直接找长度 $=3$ 的即可。

暴力的做法是考虑数组计数，由于是排列，前面没出现过后面一定出现，所以如果在数组计数的数组中，出现形如 $10000100000$ 的不对称情况，就说明会出现等差数列。

判断对不对称可以用哈希，然后可以用线段树优化时间复杂度。

二、和哈希

玄学东西。

1. P3792 由乃与大母神原型和偶像崇拜

最人机的想法，维护区间的最大和最小值，在维护区间和，判断区间和是否等于 $(min+max)\times len÷2$。

但这随便 hack，1 3 3 3 5 就会被判断可以，但实际上并不行。

所以开始乱搞，可以维护区间平方和，判断是否等于 $\sum _{i=min}^{max}{i}^2$。

这题数据水，这样就过了，实际上，还可以维护区间立方和，$i^i$ 的和，……

2. P8819 [CSP-S 2022] 星战

有个比较不帅的结论：满足要求二一定能满足要求一，因为这是张有向图，每个点出度都为 $1$ 不走成环还能怎么走？

接下来的四种操作就是：入度减一，入度归零，入度加一，入度还原。

跟上题一样，人机的想法就是判断入度和是不是等于 $n$，但显然错。

然后乱搞，为什么每个点连一条边入度都一定加一？直接给每个点随机一个权值，指向别的点的时候让别的点加上我的权值，再判断入度和是不是等于随机权值和即可。

三、树同构

就是说，无向的树在不考虑编号的前提下，树的形状是否相同。

根据哈希，肯定需要满足分配律，我这里直接贴 lby 大佬的乘法分配律 & 加上子树大小的牛求法：

$$h_u=\prod _{i=1}(h_v\times bas{e}^i)+s{z}_u$$

那正确性还是不能保证，因为你不知道哪个子树被乘上了几次方的 $base$，直接把子树的哈希值按从小到大排序，乘上从低到高次方的 $base$ 即可保证正确性。

1. P4895 独钓寒江雪

题意：树上全是白点，涂黑点，但不能涂相邻的，问在同构意义下本质不同的涂法的方案数。

找重心，先说一个重心的情况：

以重心为根，直接树形 dp，不考虑同构的话，这个问题应该很好求解，就不贴转移了。（设 $f_{u,0/1}$ 表示 $u$ 点不涂 / 涂黑的方案数）

接着考虑同构，如果 $u$ 子树内有 $c$ 个和 $v$ 的子树同构，那其实就相当于将 $f_v$ 的方案数插板法放进 $c$ 个同构里。所以就是

$$f_{u,0}\leftarrow f_{u,0}\times C_{f_{v,0}+f_{v,1}+c-1}^c$$$$f_{u,1}\leftarrow f_{u,1}\times C_{f_{v,0}+c-1}^c$$

答案是 $f_{rt,0}+f_{rt,1}$。

接着考虑两个重心的情况：

根据树的相关知识，两个重心一定相邻，断掉这条边，在两个子树内分别做上述 dp。

如果这两个重心的树也同构，那再插板法一次，答案为：

$$C_{f_{r1,0}+1}^2+f_{r1,0}\times f_{r2,1}$$

否则只需要这两个点别取同色即可：

$$\sum _{i=0,1}\sum _{j=0,1}{f}_{r1,i}\times f_{r2,i}[i\ne 1\wedge j\ne 1]$$