[题解] P3526 [POI 2011] OKR-Periodicity

Yansuan_HCl · 2025-03-21 14:10:53 · 题解

记号

用大写表示串，小写表示串的长度。用希腊字母表示周期，以示区分。

Border 与周期互化

若串 S 有长度为 p 的 border，则有长度为 \pi = |S|-p 的周期。

弱周期引理

若串 S 中有周期 \Pi, \Chi，其长度为 \pi, \chi，且 \bold{\pi+\chi} \le |S|，则 \gcd(\pi, \chi) 为周期。

证明：由周期关系有 s_i=s_{i\bmod \pi}=s_{i\bmod \chi}，由裴蜀定理，仅当 s 存在周期 \gcd(\pi, \chi) 时能满足条件。

分类讨论

记 f(S) 为由 S 构造出的串。取 S 的最小周期串记为 \Alpha，则 S 形如 \Alpha \ldots \Alpha \Alpha'，其中 \Alpha' 是 \Alpha 的前缀。我们希望能通过周期或 border 引入的相等关系进行递归构造。

\Alpha 完整出现至少两次

由周期性，我们希望仅通过求 f(T),T=\Alpha \Alpha ' 就能得到 f(S)；此时最小性已经满足，下面证明这样构造的串 \Beta \ldots \Beta \Beta ' 与原串具有相同的 border 集合。

设 p 为讨论的 border 长度。

• - 若 $S$ 有 border $p$，则 $f(S)$ 有 border $p$。$S$ 有对应周期 $\pi = n-p$，由 $\beta$ 是 $S$ 最小周期可知 $\beta \mid \pi$；$f(S)$ 也有周期 $\beta$，得证。 - 若 $f(S)$ 有 border $p$，则 $S$ 有 border $p$。$f(S)$ 有对应周期 $\pi = n-p < n-\beta+\beta'$。反证：若 $\beta \nmid \pi$，则存在周期 $\theta = \gcd(\beta, \pi)<\beta$；此时 $\theta$ 是 $\Beta$ 的周期，与 $\Beta\Beta'$ 最小周期为 $\Beta$ 矛盾。

\Alpha 完整出现不超过一次

此时再递归 \Alpha\Alpha' 没有意义。设 a=n-|\Alpha| 为 S 的最长 border，则 S 形如 AXA，且 x\ge 1。最好能先递归求 f(A) 再确定 X 对应的串。不妨大胆猜测 X 对应的串可以全部填 0，记 f(S)=BYB，Y 全 0。

但是这样可能引入 > a 的 border，需要调整。字典序最小的调整方法是将 Y 最后一位改为 1，记为 Z。下面证明 BZB 一定合法。

设 BYB 的最长 border c > a，其对应的周期为 \sigma=n-c 为 BYB 的最小周期。由 border a，BYB 有周期 \alpha=n-a=a+x，此时 \sigma \mid \alpha，即 \Sigma 是 BY 的整周期。

• 若 \sigma \le x，则 BY 为全 0 串；此时将 Y 换成 Z 一定合法。

此时 \sigma >x，\Sigma=DY，其中 D 是非全 0 的串。则 BYB=(DY)^kD\red{Y}(DY)^kD，BZB=(DY)^kD\blue{Z}(DY)^kD。

反证：设 BZB 有 border e>a。

• 若 e < a+x，则前后 e 个字符中 1 的数量不同，不合法。
• 否则 e\ge a+x。BZB 有周期 \epsilon=n-e \le \alpha-x<\alpha，可推出有周期 \theta=\gcd(\alpha, \epsilon) <\epsilon。
  • 当 \epsilon < a-d，即 e > a+x+d 时：
  • 且 \theta \le \epsilon < a-d = k\sigma。
  • 若 \sigma \nmid \theta，则 (BY)^k 有周期 \gcd(\sigma, \theta) < \sigma，矛盾。
  • 因此，\theta = k'\sigma \le k\sigma，BZB 有循环节 (DY)^{k'}，可推出 DY=DZ，矛盾。
  • 当 \epsilon \ge a-d，即 e \le a+x+d 时：
  • 取出 E 长为 \sigma 的后缀 F，则 F=D[e-(a+x),d)ZD[0,e-(a+x))；由 border，F=(BZB)[n-\sigma, n)=YD。F 与 YD 间 1 的数量不同，矛盾。

故得证。

每次递归规模减少到不超过 \frac 2 3 n，时间复杂度 O(n)。