[ABC362G] Count Substring Query 乱搞记

前言

ABC 出题人喜欢出板子是吧，像这种出题人就应该好好用乱搞拷打一下。

拜谢 @RailgunZzzz 以及其他 HL 群群友在卡常和卡哈希时给予的若干帮助。

先处理出整串哈希，然后我们考虑根号分治。

设根号分治的阈值为 $T$ ，则有两种算法可以用来回答询问：

对长度 $>T$ 的串暴力。求出被询问的串的哈希，从左到右枚举被匹配的子串的右端点，把两个哈希 $\mathcal{O}(1)$ 进行比较，单次询问复杂度 $\mathcal{O}(n)$ 。设 $sum=\sum |t|$ （ $t$ 为被询问的串），长度 $>T$ 的串最多被询问 $\mathcal{O}(\frac{sum}{T})$ 次，所以这部分时间复杂度为 $\mathcal{O}(n\frac{sum}{T})$ 。
对长度 $\leq T$ 的串预处理。预处理原串所有长度 $\leq T$ 的子串的哈希值，扔到 $T$ 个 vector 里进行排序，类似于离散化，每次回答时二分询问串的哈希在 vector 里的位置即可得知它出现了几次。这部分预处理的时间复杂度为 $\mathcal{O}(Tn\log n)$ ，单次回答复杂度 $\mathcal{O}(\log n)$ 。

对以上两种算法进行根号平衡，列均值等式解得 $T≈\sqrt{\frac{sum}{\log n}}$ ，算法总复杂度为 $\mathcal{O}(n\sqrt{sum\log n})$ ，理论可过，但常数巨大，需要进一步优化。

我们的阈值里面带了一个 $sum$ ，而求出 $sum$ 的唯一办法就是将询问离线，可是开一个大小为 $q$ 的 string 数组无疑会带来巨大的常数开支，于是考虑多尝试几种阈值。

经过测试，取 $T=\frac{\sqrt q}{\log n}$ 时，是所有阈值里运行速度最快的，推测：显然这个 $T$ 值比计算的 $T$ 值小，会让更多的串去跑暴力，而暴力解法常数较小。

尝试了无数种卡常方式之后，发现尽管是无法保证正确性的单模哈希，在题目时限下都无法通过。在这种情况下，我们只能使用 unsigned int 自然溢出处理哈希（连 unsigned long long 自然溢出都会 TLE）。

裸的自然溢出交上去是这样的，使用 BingFS 搜索卡自然溢出的方法，发现哈希 base 为偶数时极其容易被卡掉，而奇数 base 相对难卡很多。于是引出下一种乱搞：随机 base。

使用一个 mt19937 在预处理时生成随机 base 即可，这部分比较简单，加上之后虽然还是无法通过，但 WA 的测试点数量已经大幅降至了 $1$ 至 $4$ 个。

我们充分利用人类智慧，发现询问的串长度越小，是出题人故意造出来 hack 自然溢出的概率就越高。于是我们在算法的第二部分放弃自然溢出，换用准确度接近 $100\%$ 的双模哈希来处理长度 $\leq T$ 的串，而在第一部分的暴力解法中仍然使用自然溢出，最大限度发挥暴力常数小的优势。

经过上述所有优化之后的代码平均提交 $6$ 次就可以取得一次 AC。