题意
给定一个字符串 \(s\)。
设一个字符串 \(t\) 是好的,当且仅当不存在一个 \(\text{Period}\) 能整除 \(|t|\)。
求最小的划分段数使得每段都是好的,及最小的划分段数的方案数。
Sol
考虑两种特殊情况:
- \(s\) 有长度为 \(1\) 的 \(\text{Period}\)。
- \(s\) 本身就是好串。
前者答案显然为 \((n, 1)\),后者答案为 \((1, 1)\)。
集中注意力,不难想到一个结论:
最小的划分段数只会为 \(2\)。
显然可以考虑对于某个不好的串,可以考虑将她的最后一个字母割开。
注意到对于后面的这个串,我们一定可以找到某一个后缀串,可以使得她是好的串。
否则若 \(s\) 的所有后缀都是不好的串,那么 \(s\) 显然存在长度为 \(1\) 的 \(\text{Period}\)。
因此,证明该结论即证:对于所有的 \(s'\) 与 \(s' + c\) (\(c\) 为一个字符),两者不可能同为好串。
其实这个结论非常好证明。
首先,根据 \(\text{Periodicity Lemma}\) 可知:
若一个串有 \(\text{Period}\) \(p, q\),且 \(p + q \le |S| + \gcd(p, q)\),则 \(\gcd(p, q)\) 为该串的一个 \(\text{Period}\)。
显然,对于 \(s'\) 的整除 \(|s'|\) 的 \(\text{Period}\) \(x\),与 \(s' + c\) 的 \(\text{Period}\) \(y\)。
\(x \le \frac{|s'|}{2}\),\(y \le \frac{|s'| + 1}{2}\),所以 \(x + y \le |S| + \gcd(x, y)\)。
又因为 \(x\) 为 \(s'\) 的一个 \(\text{Period}\),所以 \(\gcd(x, y)\) 为 \(s'\) 的一个 \(\text{Period}\)。
显然 \(\gcd(x, y)\) 只能为 \(1\)。
对于长度为 \(1\) 的 \(\text{Period}\),已经被我们判过了。
所以结论成立。
对于第二问,考虑枚举每一个分割点,判断前后两段是否为好串即可。
根据 \(\text{Periodicity Lemma}\) 可知,直接判断最小 \(\text{Period}\) 是否整除即可。
标签:le,gcd,一个,text,Period,ARC060F,Representation,整除,Best From: https://www.cnblogs.com/cxqghzj/p/18121717