CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

===== 题解 =====

这个题要是从runs是什么以及怎么求开始讲那得到下辈子讲完了，就捞干的说点结论。

首先，runs是一个三元组构成的集合，其中 $(l,r,p)$ 表示 $S[l,r]$ 的最小周期是 $p$ ，且 $S[l-1]!=S[l-1+p]$ 且 $S[r+1]!=S[r+1-p]$ ，同时 $r-l+1 \ge 2p$。这里有一些比较神秘的点，就是这个周期不一定是整周期，只需要一直满足 $S[i]=S[i+p]$ 即可。

然后，我们定义了一个叫 Lyndon根 的东西。这玩意是说，在每个三元组中，找到其一个长度是 $p$ 的子串，在给定偏序关系下是 Lyndon串，那么这玩意就是它的 Lyndon根。之后我们考虑求出来每个位置向后的最长的 Lyndon串，由于每个三元组的 Lyndon根 必然形如 $S[i,ly(i)]$ ，那么我们就可以通过求出来之后向两侧扩展来得到这个三元组了。

首先有一个重要的结果是，本源平方串个数是 $O(n\log{n})$ 的。

然后每个平方串都会在一个三元组中，那么我们就可以通过在每个三元组中枚举平方串的方式来得到我们所有可能的平方串了。这样我们枚举的时候，取到一个 $S[l+a,l+a+2kp-1]$ 的时候，我们可以将其与 $S[l+a+2(k-1)p,l+a+2kp-1]$ 这个本源平方串对应起来。所以枚举的时间也就是 $O(n\log{n})$ 的，可以接受。枚举完之后，我们将其在这个三元组中出现次数和其一半在S中出现次数乘起来作为贡献即可。

总时间复杂度就是 $O(n\log^2n)$ 。

CVBB ACM Team

用户工具

站点工具

页面工具