题解 CF1056E 【Check Transcription】
brealid
·
·
题解
说一个关于 Hash 的复杂度证明（下文中 S_{01} 表示 01 串，S_{abc} 表示字母串）
通常这道题的 Hash 做法流程是这样的（记 cnt_0 为 01 串中的 0 个数，cnt_1 为 01 串中的 1 个）
- 枚举 r_0 的长度 len_0
- 如果根据枚举到的长度 len_0 可以找到一个正整数 len_1，满足 cnt_0 * len_0 + cnt_1 * len_1 = |S_{abc}|，那么进行第 3 步，否则枚举下一个 len_0
- 扫一遍 S_{01}，同时维护一个指针 p 指向 S_{abc} 中的字符（初始为 1）。如果遇到 0，则将 ^{\mathbf{Hash}}r_{0} 与 Hash(p, p + len_0 - 1) 比较（若当前枚举到的 0 是 S_{01} 的第一个 0，则将 ^{\mathbf{Hash}}r_{0} 设为 \mathbf{Hash}(p, p + len_0 - 1)），同时将指针加上 len_0。遇到 1 同理。
对于这样一个过程，枚举 len_0 的复杂度是 \Theta(\frac{|S_{abc}|}{cnt_0})
考虑对于多少种情况，存在满足 cnt_0 * len_0 + cnt_1 * len_1 = |S_{abc}| 的 len_1
由 \mathbf{exgcd} 的知识，可知两组满足条件的 \begin{cases}len_0\\len_1\end{cases} 之间，len_0 相差 \frac{cnt_0}{\mathbf{gcd}(cnt_0, cnt_1)}
因此最多需要扫
\frac{\Theta(\frac{|S_{abc}|}{cnt_0})}{\frac{cnt_0}{\mathbf{gcd}(cnt_0, cnt_1)}}=\Theta(\frac{\mathbf{gcd}(cnt_0, cnt_1)*|S_{abc}|}{cnt_0^2})
遍的 S_{01}，每次 \Theta(|S_{01}|)
总时间复杂度
\Theta(\frac{\mathbf{gcd}(cnt_0, cnt_1)*|S_{abc}|*|S_{01}|}{cnt_0^2})
其中，
\max\{\mathbf{gcd}(cnt_0, cnt_1)\}≈\frac{|S_{01}|}{2}
$cnt_0$ 显然可以通过倒置 $0,1$ （$0$ 变 $1$，$1$ 变 $0$）变成 $\max\{cnt_0, cnt_1\}$）
$$\therefore\Theta(\frac{\mathbf{gcd}(cnt_0, cnt_1)*|S_{abc}|*|S_{01}|}{cnt_0^2}) = \Theta(\frac{|S_{01}|*|S_{abc}|*|S_{01}|}{|S_{01}|^2})=\Theta(|S_{abc}|)$$
---
时间复杂度是优于 $\mathbf{SA}$ 的。
但由于自动溢出 $2^{32}$ 被卡了（$2^{64}$ 尚不清楚），所以需要 ``long long`` + ``% P``(P 是质数)，因此有一个较大的常数。
不过还是比 $\mathbf{SA}$ 快 
代码可以见 [gitee 仓库](https://gitee.com/hkxa/mycode/blob/master/luogu/CF1056E.cpp)