P3526 [POI2011]OKR-Periodicity
nb 题。
先说一下这题的入手点。不妨假设一个字符串一定存在一个短周期（约定周期 \(p\) 满足 \(2p\leq |s|\) 的为短周期），假设短周期的长度为 \(l\)，那么可以说明所有长度小于 \(|s|-l\) 的周期都能写成 \(kl,k\in\mathbb{Z}\) 的形式，所以我们只需要关注长度在 \(|s|-|s|\bmod l\sim |s|\) 之间的周期即可，其它的部分都是重复的循环节。所以我们把这部分单独提出来，设为 \(t'\)，且保证 \(s\) 可以表示成 \(tt\cdots t'\) 的形式，显然我们只需要构造 \(tt'\) 即可。假设 \(\text{solve}(s)\) 为构造和 \(s\) 周期相同的串，那么可以把 \(s\) 分解，执行 \(qq'=\text{solve}(tt')\)，其中 \(q,q'\) 分别与 \(t,t'\) 对应，然后将前面的 \(q\) 重复就好了。
关键问题在于字符串不存在短周期的情况，关键问题在于我们并不能用上面的方法减小问题规模。转而考虑 border，存在长周期意味着存在短 border，能不能尝试构造 border 来缩小规模呢？不妨设字符串的最长 border 为 \(t\)，那么 \(s=tat\)，我们的目的是构造 \(t\) 之后构造字典序尽可能小的 \(a\) 来使得原串不存在更长的 border。
直接探索合法条件过于复杂，不妨考虑特殊情况。字典序最小的 \(a\) 为全 \(0\) 串，考虑判断全 \(0\) 串是否合法。如果不合法，即存在更长的 border \(l\)，假设 \(l\) 是最长 border，我们分类讨论 \(l\) 的长度：
- \(l\leq |t|+|a|\)，此时 border 的形态为 \(ta'\) 和 \(a't\)，其中 \(a'\) 表示削减了一定长度的全 \(0\) 串，由此可以推得 \(t\) 是一个全 \(0\) 串。那么使之合法的方法是把 \(a\) 的最后一个字符变为 \(1\)。
- \(l>|t|+|a|\)，此时有 \(2|t|+|a|-l\) 为原串周期，且是最短周期。由于 \(|t|+|a|\) 也是原串周期（\(t\) 是原串 border），有 \(2|t|+|a|-l\) 为 \(|t|+|a|\) 因数，所以 \(ta\) 是一个整周期串，进一步地，\(ta\) 一定可以表示成 \(baba\cdots ba\)，其中 \(b\) 是一个非全 \(0\) 的串。容易发现这就是存在更长 border 的充分必要条件。那么如果继续沿用上面做法，将 \(a\) 的最后一个字符替换成 \(1\) 呢？假设仍然存在 border，可以发现，\(a'\) 的末尾字符必然和字符串 \(b\) 的一个字符相匹配，假设为 \(b_i\)，分类讨论：
- \(i\leq |a|\)，画图可以发现 \(b\) 存在长度为 \(|b|-i\) 的 border，即长度为 \(i\) 周期。所以 \(b\) 的末尾 \(i\) 个字符一定是 \(|a|\) 的 \(i\) 后缀的一个循环移位（rotate），那么 \(b\) 的末尾 \(i\) 个字符一定存在一个 \(1\)，而它对应的是一个 \(a\) 的前缀，矛盾。
- \(i>|a|\)，此时 \(b\) 的 \(i\) 前缀由 \(ca'\) 组成，且 \(b\) 仍然存在一个 \(|b|-i\) 的 border，且 \(b\) 的 \(|b|-i\) 后缀为 \(ac\)（考虑 \(a'\) 前面的 \(b\)），那么 \(ac=ca'\)，这两个 \(1\) 的个数都不相同，矛盾。
所以如果不合法的话，替换成 \(00\cdots 01\) 就是合法的，而这显然非常优秀。所以综上，对于只存在短 border 的串，我们可以通过构造 border，并调整中间串使字符串合法。
观察可以发现我们每次都让串长减小一般，总时间复杂度为 \(T(n)=T(n/2)+\mathcal{O}(n)=\mathcal{O}(n)\)。
梳理整个思维过程就是：
- 通过存在短周期这一特殊条件，考虑归纳构造思路，进而发现长周期的特殊情况。
- 观察到长周期的本质问题在于构造中间串，通过判断全 \(0\) 串是否合法的特殊情况，分类讨论探索性质并得到最终合法构造。