[Mivik Round / Secret Sky] [题解] Shelter
Mivik
·
2021-04-15 23:52:54
·
题解
如果没有 border，答案是 n 。
如果有整周期，则答案是 |p|+2^K(n-|p|) ，其中 p 是最小整周期。
如果 border 大于 \dfrac n2 ，即周期小于 \dfrac n2 。令 s=p^k\cdot pre_t(p) ，其中 p 是最小周期，pre_t(p) 是 p 的长为 t 的前缀（0<t<|p| ）。实际上这样的字符串进行一次操作之后的最长 border 仍为 n-p ，证明如下：
假设进行一次操作后的字符串有一个长度小于 n 的周期 q ，首先我们知道 p\nmid q ，因为如果 q 是 p 的倍数的话就间接指出 p^\infty=pre_t(p)\cdot p^\infty ，则 t 是 p 的整周期，p 就不是原串的最小周期了。于是我们知道 q>\dfrac n2 ，因为 p\nmid q ，如果 q\le \dfrac n2 ，则会必然会有一个小于 p 的周期（弱周期引理）。不难发现由于 |p|\le\dfrac n2 ，于是 k>1 ，那么根据周期的定义，我们知道 q=suf_{n-|q|}(s)\cdot pre_{2|q|-n}(p^\infty) （把 q 重复两次和串匹配），于是我们得知 (|q|\bmod|p|) 和 (|p|-(|q|\bmod|p|)) 同为 p 的周期，进而通过周期引理我们知道 p 必然有一个长为 g=(|q|\bmod|p|,|p|) 的周期，而由于 g<|p| 且 g\mid(|p|) ，我们知道 g 是 p 的一个整周期，则 g 也是原串的一个周期且长度小于 p ，形成矛盾。于是我们得证。
这样的话，一个周期小于 \dfrac n2 的字符串经过一次操作之后 border 仍为 n-p ，那么此时的最短周期就为 n+(n-p)-(n-p)=n>\dfrac{n+(n-p)}2 。于是我们现在只需要讨论周期大于 \dfrac n2 的情况。
对于这种情况，即 k=1 ，我们有一个结论。令 B 为 s 的最长 border，l 为 B 的最小整周期，令 B=l^j ，然后找到最大的 i 使得 pre_{i|l|}(s)=l^i 。首先 i|l|<n+|l| ，因为反之的话，首先我们知道 |l|\nmid n （s 有一个整周期的情况我们已经在题解最开始讨论过了），于是我们知道 i|l|-n\ge |l| ，不妨令 n\equiv q\pmod{|l|} ，则 suf_{|l|-q}(l) 既是 l 的周期也是 l 的 border，于是 l 会有一个更小的整周期，形成矛盾。
有个结论：我们进行第 b 次操作后的最长 border 长度为 \min\{2^bj,i\}|l| 。考虑归纳证明。b=0 时显然，我们考虑 b>0 。在进行这一操作前的字符串，假令其长度为 n ，我们知道最长 border 长度是 \min\{2^{b-1}j,i\}|l| 的，那么显然进行这一操作后的字符串会有一个长为 \min\{2^bj,i\}|l| 的 border，我们只需要证明不存在一个比其更长的 border。
- $|\text{border}|=l^k$：这意味着 $l^k=l^i\cdot s_{[i|l|,k|l|]}$。由于 $k>i$，这显然不可能，因为这意味着 $pre_{(i+1)|l|}(s)=l^i$，则我们的 $i$ 是应该更大的，产生矛盾。
- $|\text{border}|\ne l^k$：假令 $|\text{border}|\equiv q\pmod l$，$|\text{border}|=d$，则我们得到 $l^i\cdot s_{[i|l|,d]}=suf_q(l)\cdot l^{\left\lfloor\dfrac d{|l|}\right\rfloor}$。由于 $\dfrac{d}{|l|}\ge i$，我们知道 $l=suf_q(l)\cdot pre_{|l|-q}(l)$，即 $q$ 既是 $l$ 的周期也是 $l$ 的 border，则 $l$ 有一个更小的整周期，产生矛盾。
于是我们只需要找到 i,j 后直接模拟即可，时间复杂度 O(n+\log K) （s 有整周期时的快速幂）。
mivik.h / 代码