专栏文章

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

YYansuan_HCl
P3526题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipuztgq
此快照首次捕获于
2025/12/03 18:23
3 个月前
此快照最后确认于
2025/12/03 18:23
3 个月前
查看原文

记号

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

Border 与周期互化

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

弱周期引理

若串 SS 中有周期 Π,X\Pi, \Chi，其长度为 π,χ\pi, \chi，且 π+χ≤∣S∣\bold{\pi+\chi} \le |S|，则 gcd⁡(π,χ)\gcd(\pi, \chi) 为周期。
证明：由周期关系有 si=si mod π=si mod χs_i=s_{i\bmod \pi}=s_{i\bmod \chi}，由裴蜀定理，仅当 ss 存在周期 gcd⁡(π,χ)\gcd(\pi, \chi) 时能满足条件。

分类讨论

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

A\Alpha 完整出现至少两次

由周期性，我们希望仅通过求 f(T),T=AA′f(T),T=\Alpha \Alpha ' 就能得到 f(S)f(S)；此时最小性已经满足，下面证明这样构造的串 B…BB′\Beta \ldots \Beta \Beta ' 与原串具有相同的 border 集合。
设 pp 为讨论的 border 长度。
  • p≤β+β′p \le \beta + \beta '，显然已经满足。
  • p>β+β′p > \beta + \beta '：
    • 若 SS 有 border pp，则 f(S)f(S) 有 border pp。SS 有对应周期 π=n−p\pi = n-p，由 β\beta 是 SS 最小周期可知 β∣π\beta \mid \pi；f(S)f(S) 也有周期 β\beta，得证。
    • 若 f(S)f(S) 有 border pp，则 SS 有 border pp。f(S)f(S) 有对应周期 π=n−p<n−β+β′\pi = n-p < n-\beta+\beta'。反证：若 β∤π\beta \nmid \pi，则存在周期 θ=gcd⁡(β,π)<β\theta = \gcd(\beta, \pi)<\beta；此时 θ\theta 是 B\Beta 的周期，与 BB′\Beta\Beta' 最小周期为 B\Beta 矛盾。

A\Alpha 完整出现不超过一次

此时再递归 AA′\Alpha\Alpha' 没有意义。设 a=n−∣A∣a=n-|\Alpha| 为 SS 的最长 border，则 SS 形如 AXAAXA，且 x≥1x\ge 1。最好能先递归求 f(A)f(A) 再确定 XX 对应的串。不妨大胆猜测 XX 对应的串可以全部填 00，记 f(S)=BYBf(S)=BYB，YY 全 0。
但是这样可能引入 >a> a 的 border，需要调整。字典序最小的调整方法是将 YY 最后一位改为 1，记为 ZZ。下面证明 BZBBZB 一定合法。
设 BYBBYB 的最长 border c>ac > a，其对应的周期为 σ=n−c\sigma=n-c 为 BYBBYB 的最小周期。由 border aa，BYBBYB 有周期 α=n−a=a+x\alpha=n-a=a+x，此时 σ∣α\sigma \mid \alpha，即 Σ\Sigma 是 BYBY 的整周期。
  • 若 σ≤x\sigma \le x，则 BYBY 为全 0 串；此时将 YY 换成 ZZ 一定合法。
此时 σ>x\sigma >x，Σ=DY\Sigma=DY，其中 DD 是非全 00 的串。则 BYB=(DY)kDY(DY)kDBYB=(DY)^kD\red{Y}(DY)^kD，BZB=(DY)kDZ(DY)kDBZB=(DY)^kD\blue{Z}(DY)^kD。
反证：设 BZBBZB 有 border e>ae>a。
  • 若 e<a+xe < a+x，则前后 ee 个字符中 1 的数量不同，不合法。
  • 否则 e≥a+xe\ge a+x。BZBBZB 有周期 ϵ=n−e≤α−x<α\epsilon=n-e \le \alpha-x<\alpha，可推出有周期 θ=gcd⁡(α,ϵ)<ϵ\theta=\gcd(\alpha, \epsilon) <\epsilon。
    • 当 ϵ<a−d\epsilon < a-d，即 e>a+x+de > a+x+d 时：
      • θ=gcd⁡(α,ϵ)=gcd⁡(ϵ,a+x−ϵ)>d+x=σ\theta = \gcd(\alpha,\epsilon) = \gcd(\epsilon, a+x-\epsilon)> d+x=\sigma；
      • 且 θ≤ϵ<a−d=kσ\theta \le \epsilon < a-d = k\sigma。
      • 若 σ∤θ\sigma \nmid \theta，则 (BY)k(BY)^k 有周期 gcd⁡(σ,θ)<σ\gcd(\sigma, \theta) < \sigma，矛盾。
      • 因此，θ=k′σ≤kσ\theta = k'\sigma \le k\sigma，BZBBZB 有循环节 (DY)k′(DY)^{k'}，可推出 DY=DZDY=DZ，矛盾。
    • 当 ϵ≥a−d\epsilon \ge a-d，即 e≤a+x+de \le a+x+d 时：
      • 取出 EE 长为 σ\sigma 的后缀 FF，则 F=D[e−(a+x),d)ZD[0,e−(a+x))F=D[e-(a+x),d)ZD[0,e-(a+x))；由 border，F=(BZB)[n−σ,n)=YDF=(BZB)[n-\sigma, n)=YD。FF 与 YDYD 间 1 的数量不同，矛盾。
故得证。
每次递归规模减少到不超过 23n\frac 2 3 n，时间复杂度 O(n)O(n)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...