题解 ARC060D

1kri · 2022-04-11 19:51:38 · 题解

首先特判几种情况：

1. 所有字母全相等，答案二元组显然为 (n,1)。
2. 字符串本身就是 \text{good string}，答案二元组为 (1,1)。

否则可以证明答案为 2，因为在 S 最后一个字母前把串割开，前一部分一定不是 \text{good string}。

这个结论等价于对于两个不由同一种字母构成的字符串 S 和 S+c （指在 S 后加一任意字母），它们不可能同时为 \text{good string}。

考虑反证，假设有最小的 x 满足 x \in \text{Period}(S+c) 且 x\mid(|S+c|)，有最小的 d 满足 d \in \text{Period}(S) 且 d\mid(|S|)。

则显然有 x \leq \frac{|S|+1}{2}，d \leq \frac{|S|}{2}，x\in \text{Period}(S)。那么 x+d-\gcd(x,d)\leq |S|，由 \text{Periodicity lemma} 得 \gcd(x,d) \in \text{Period}(S)。

由 d 的最小性可知 d|x，故 d\mid(|S+c|)，即 d\mid(|S|+1)。

又因为字符串不由同一种字母构成，所以 d>1，所以 d 不可能同时为 |S| 和 |S|+1 的因数，与原假设矛盾，故原假设不成立，因而结论得证。

知道这个结论后，我们可以枚举每一个分割点，并判断两部分是否为 \text{good string}。判断过程可以直接 \text{kmp} 找最小 \text{Period} 并判断是否整除。

时间复杂度：O(|S|) 。