P14363题解

我们充分发扬人类智慧，考虑对着这个限制直接统计，使用字符串哈希，那么 $s_{i,1}$ 与 $s_{i,2}$ 能够成功替换当且仅当 $\text{Hash}_{t_1}+P^k(\text{Hash}_{s_{i,2}}-\text{Hash}_{s_{i,1}})=\text{Hash}_{t_2}$ 其中 $P$ 是钦定的哈希基数，$k$ 与这个位置到串的结尾的距离有关，当然还需要满足 $s_{i,1}$ 在 $t_1$ 中出现过。

先从第一个式子考虑起，我们将这个式子变形。 $\frac{\text{Hash}_{t_2}-\text{Hash}_{t_1}}{P^k}=\text{Hash}_{s_{i,2}}-\text{Hash}_{s_{i,1}}$ 注意到当你的哈希模数为质数时，是可以提前处理出 $P^k$ 的逆元的，于是左边式子的值在枚举结尾的位置时就成了定值，相当于我们要查找有多少对 $(s_{i,1},s_{i,2})$ 满足 $\text{Hash}_{s_{i,2}}-\text{Hash}_{s_{i,1}}=t$，直接使用手写哈希表统计就行了。

在具体实现中，哈希表中这一位的数不一定满足要求，所以我们需要遍历每一位，判断 $s_{i,1}$ 是否在 $t_1$ 中出现过。

但这时候就会出现一个问题，就是 b 的哈希值 $-$ a 的哈希值与 c 的哈希值 $-$ b 的哈希值相同，这样会使复杂度退化，这是我们不希望看到的，于是我们充分发扬人类智慧，考虑对 $26$ 个字符随机分配一个哈希权值 $Val$。这样就保证了如果两对字符串不同，随机数据下，那么它们的哈希差不同且在哈希表中是均匀分布的，这样就保证了我们暴力查找判断的复杂度。

这么做复杂度约为 $O(L)$，随机数据直接吊打一众二维数点做法，约为线性，但常数巨大，因为有一堆乘法与取模，但是可以被特殊数据卡到超时，但在考场上不失为一种好做法。

代码等拿到了再放，考场上写这玩意结束前半小时才调出来，没时间写 $\text{T4}$，痛失 $\text{AK}$，不过这是不是我正赛中切的最牛的一道题。