自动搬运

查看原文

来自洛谷，原作者为

	dspt その日まで 飛ばあげ 嵐がさわってゆくまで

搬运于2025-08-24 22:56:23，当前版本为作者最后更新于2024-03-25 15:11:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

String Round Rank 6 纪念，场切了此题，写篇题解。

题目涉及了 Border，显然可以跟 KMP 结合，此外就是一些分类讨论了。

性质

1. 长为 $n$ 的字符串 $S$ 为周期字符串等价于：存在长为 $k$ 的字符串 $T$，满足：$k|n$，$S$ 与 $\frac nk$ 个 $T$ 拼接而成的字符串等价。$k$ 被称为 $S$ 的一个周期。
2. 满足条件一的最小的 $k$ 被称为字符串 $S$ 的最小周期。
3. 若长为 $n$ 的字符串 $S$ 为周期字符串，记其最长真 border 的长为 $m$，若 $S$ 存在周期 $n-m$，则 $n-m$ 为 $S$ 的最小周期。

这些性质的证明可以见有关 KMP 的文章。

分类讨论

我们使用 KMP 求出 $S$ 的最长真 border $T$，令 $n=|S|,k=|T|$，下面对 $T$ 进行分类讨论。

1：$T$ 为空

显然每次根本无法拓展，答案即为 $(R-L+1)n$。

2：$|T|$ 为 $S$ 的一个周期

假设已用 KMP 求出最长真 border $T$，判断 $k$ 是否为 $S$ 的周期是简单的。

由于拓展的字符串需要是真 border，每次拓展的长度即为 $|S'|-k$，拓展 $i$ 次后的 $|S'|$即为 $2^in-(2^i-1)k$，求和得 $(2^{R+1}-2^L)(n-k)+(r-l+1)k$，快速幂计算即可。

3：$T$ 不是周期字符串

注意：此情况的前提是不满足前两个情况。

显然每次拓展的长度均为 $k$，拓展 $L$ 次后长度为 $n+Lk$，$R$ 次后长度为 $n+Rk$，求和得 $(R-L+1)n+\frac{(L+R)(R-L+1)}2k$。

4：$T$ 是周期字符串

注意：此情况的前提是不满足前两个情况。

此情况的讨论应该是最容易漏掉的一种，$T$ 是否是周期字符串跟 $S$ 是否是周期字符串同理，容易判断。

设 $T$ 的最小周期为 $p$，且 $S[1:p]$ 在 $S$ 的前缀中重复了 $a$ 次，$S[1:p]$ 在 $S$ 的后缀中重复了 $b$ 次。

例如：$S=$abababcabab，则 $T=$abab，$p=2$，$S[1:p]=$ab 在 $S$ 的前缀中重复了 $a=3$ 次，在 $S$ 的后缀中重复了 $b=2$ 次。

这时的拓展情况应该是怎样的呢？不难发现每次向后拓展 $\min(a,b)$ 个 $S[1:p]$。

将 $\min$ 拆开助于思考：

1. 在 $a\geqslant b$ 时，每次拓展 $b$ 个 $S[1:p]$，同时 $b\leftarrow 2b$，这样的拓展不超过 $\log_2n$ 次，可以暴力枚举。
2. 在 $a<b$ 时，每次拓展 $a$ 个 $S[1:p]$，由于 $a$ 这个数值不会变，所以容易计算出。

具体地，计算第一部分暴力维护长度 $S'$ 和拓展次数 $i$，若 $i\in[L,R]$，将答案加上 $S'$。第二部分仅在 $R>i$ 时有贡献（$i$ 是完成第一部分的拓展次数），由于每次拓展长度固定，可以用情况三的式子计算。

容易发现第三种情况和这种情况类似，可以令 $a=b=1,p=k$，合并到一起计算。