题解 P3526 【[POI2011]OKR-Periodicity】

· · 题解

同步发布于cnblogs

Updated On 2022.02.01：情况 4 细节添加，也算是解决了第一次做这个题的时候一些口胡上的疑惑

2011年就能出出这样充满科技感+脑力的题，佩服POI Orz

约定：字符串 s 的下标从 0 开始，s_{i,j} 表示 s 的第 i 到第 j 个字符构成的子串。

串 s 有长度为 l 的周期等价于其有长度为 |s|-l 的 border。

设函数 solve(s) 表示字典序最小的、border 集合与 s 的 border 集合相同的 01 字符串。分为以下情况：

  1. 如果 s 中所有字符相同，返回 |s| 个 0 构成的字符串；
  2. 如果 s 周期集合为空，返回 |s| - 1 个 0 接上 1 个 1 构成的字符串；
  3. 如果 s 最短的周期长度 len 满足 2len \leq |s|，设 t = s_{1,len}，则 s 可表示为 ttt...tt' 的形式，其中 t' 是 t 的一个前缀，可为空。
  4. 如果 s 最短的周期长度 len 满足 2len > |s|，设 border 为 t，那么 s 就可以表示为 tat 的形式，其中 a 是一个任意字符串，不能为空。

1 和 2 情况的构造是显然的。

对于 3 情况，递归进入 tt' 求解。设 qq' = solve(tt')，那么就把 q 重复若干次拼上 qq'，即可得到答案。

在证明正确性前先来复习有关周期和 border 的几个 OI 界众所周知的简单定理。

Proof. 设 p < q，令 d = q - p。因为 p + q \leq |s|，所以 \forall i \in [0,|s|-1] , i - p \geq 0 和 i+q < |s| 至少有一个成立，故可以先向后跳 q 再向前跳 p，或者先向前跳 p 再向后跳 q，可得 s_{i+d} = s_i。那么 q-p 也是 s 的周期。根据辗转相除法，\gcd(p,q) 也是 s 的一个周期。QED

Proof. 首先这些元素一定会包含在 border 集合内。考虑使用反证法证明不存在其他的元素。

设有不满足该形式的 border 长度 l'，不妨设 l' = xl+(|s| \bmod l)+y(y \in [1,l-1])。那么在 s 的长度为 (x+1)l + (|s| \bmod l) 的前缀中，l' 是它的一个 border，即 l-y 是这个前缀的周期，而 l 也是其周期，且因为 x \geq 1 有 (x+1)l + (|s| \bmod l) \geq 2l-y，根据 Periodicity Lemma 有 \gcd(l,l-y) 是这个前缀的周期，同时 \gcd(l,l-y) \mid l 所以 \gcd(l,l-y) 是原串的一个周期，与 l 是 s 的最短周期长度不符。QED

根据推论我们可以知道如果 q 串不是满周期串（即可划分为若干个部分满足各个部分的字符串完全相同），那么 \geq |qq'| 的所有 border 都可以正确构造，而构造 qq' 的时候将 < |qq'| 的所有 border 都已经正确构造了，所以这样就是对的。

证明 q 不是满周期串是简单的：如果 q 是满周期串，不妨设 q = p^c，其中 p 是一个字符串。那么 |qq'|-|p| 是 qq' 最长的 border。而如果在原串中有这样的一个 border 且 q 是周期，那么可以立即导出 p 是周期，那么 q 就不是最小周期。

对于 4 情况，先递归进入 s_{1,len} 求解。设 t = solve(s_{1,len})，那么我们需要确定一个字典序最小的字符串 a 满足 s=tat 的最长 border 为 t。

首先我们肯定希望 a 是全 0 的字符串。但是只有这一种选择显然不能覆盖所有的情况，比如 t = 0000 时这样会使得最长 border 变大导致构造不合法。考虑在什么情况下以全 0 串作为字符串 a 会导致不合法。不妨讨论有一个更长的 border l：

至此可以得出将 a 的最后一个 0 换成 1 得到的串一定是合法的，而它显然是最优的。

梳理一下 solve(s) 的流程：

  1. 如果 s 中所有字符相同，返回 |s| 个 0 构成的字符串；
  2. 如果 s 周期集合为空，返回 |s| - 1 个 0 接上 1 个 1 构成的字符串；
  3. 如果 s 最短的周期长度 len 满足 2len \leq |s|，将 s 表示为 ttt...tt' 的形式，其中 t' 是 t 的一个前缀，可为空，设 qq' = solve(tt')，则返回 q^{\lfloor \frac{|s|}{len} \rfloor}q'；
  4. 如果 s 最短的周期长度 len 满足 2len > |s|，设 t = s_{1,len} , q = solve(t)。检验 t+000...000+t 的最长 border 是否为 len，若否将最后一个 0 替换为 1，然后将该串返回。

至于如何 check 全 0 串是否合法，暴力 KMP 一遍即可。由 T(n) = T(\frac{n}{2}) + O(n) 可得复杂度为 O(n)。