魔法面包题解¶

解法贡献：Codex（GPT-6）利用本题较小的级别上限，给出精确位编码、同块连续段递推和双向扫描，实现 \(O(nK)\) 时间、\(O(n+K)\) 空间。位编码与动态规划是已有方法；这里的贡献为本题中的组合、证明与实现。

解法比较¶

出题人解法在环串复制两遍后，分别正向和反向建立回文树，只使用长度不超过 \(n\) 的回文。对回文节点 \(v\) 和等级 \(j\) ，保存失配链上能写成同一回文块重复若干次的最长长度 \(best[v][j]\) .设 \(f\) 为其失配节点：若 \(len(v)=best[f][j]+j\) ，则取 \(len(v)\) ；否则继承 \(best[f][j]\) .

这个递推来自回文结构：若长为 \(len(v)-j\) 的后缀为回文块 \(P\) 的重复，则整个串为回文使首块也必须是 \(P\) ，故可多接一块；反之，\(P\) 的重复去掉首块仍为回文后缀，必在失配链上。每个节点为所有等级保存结果，正反两遍提供各起点的最大块数。回文树方案的时间和空间均为 \(O(nK)\) .

Codex 实现按等级逐个处理，用短二进制窗口的精确整数编码判断块是否回文及是否相同，再计算连续同块数量，立即累计最终异或值，复用临时数组。时间仍为 \(O(nK)\) ，空间降为 \(O(n+K)\) .收益是不用同时保存全部节点与等级的二维表；代价是依赖本题 \(K\le20\) 使窗口能精确装入固定字长，回文树方案对更长块仍有价值。

固定一个级别¶

固定块长 \(j\le\min(n,K)\) . 合法序列恰好是某个长度为 \(j\) 的回文块连续重复若干次。因此，只需找每个位置向左、向右最多延续多少个相同回文块。

循环数组按一个方向展开为长度 \(2n-1\) 的序列。考察下标 \(n-1\) 到 \(2n-2\) 的结尾位置（这里使用零基下标），恰好覆盖原环的每个位置一次，且每处都能看到其前面的完整一圈。

精确判断块相等与回文¶

长度为 \(j\) 的二进制块可以精确编码成一个无符号整数。由于 \(j\le20\) ，一个 32 位整数足够，无需哈希，也没有碰撞概率。

扫描新字符 \(b\in\{0,1\}\) 时，维护窗口的正向编码 \(F\) 与反向编码 \(G\) ：

\[ F'=((F\ll1)\mathbin{\mathrm{OR}}b)\mathbin{\mathrm{AND}}(2^j-1) \]

\[ G'=(G\gg1)\mathbin{\mathrm{OR}}(b\ll(j-1)) \]

窗口已经包含 \(j\) 个字符后，\(F=G\) 当且仅当该块是回文。所有块长度相同，因此前导零不影响编码的唯一性。

递推连续相同块的长度¶

令 \(f_t\) 为展开串中，以位置 \(t\) 结尾的最长合法序列长度。如果最后一块不是完整的回文块，取 \(f_t=0\) . 否则，设最后一块的编码为 \(q_t\) ：

\[ f_t=\begin{cases}j+f_{t-j},&t\ge j\ \text{且}\ q_t=q_{t-j}\\j,&\text{其他情况}\end{cases} \]

这里不存在的前驱状态按零处理。最后一块相同，才能与前驱合法序列相接；不相同就只能从当前块重新开始。按扫描位置对 \(j\) 取模，用长度为 \(j\) 的循环数组存上一块编码和递推值，访问到的恰是 \(t-j\) .

环段不能超过一圈，因此当前方向的答案为

\[ \min\bigl(f_t,\lfloor n/j\rfloor j\bigr) \]

这一步按整块截断，截取后的各块仍完全相同且为回文，因而合法。

合并两个方向¶

先按顺序扫描，记录各位置作为结尾的最大长度；再按反向扫描，得到各位置向另一个方向伸展的最大长度。取二者较大值，就是 \(a_{i,j}\) . 回文块反向后不变，因此把环段从另一端读取不会改变合法性。

每处理完一个 \(j\) ，直接把 \(j\cdot a_{i,j}\) 异或进 \(X_i\) . 只需一份长度数组和一份答案数组，不必保存所有级别的二维答案。\(j>n\) 时答案都是零，直接跳过。

复杂度与边界¶

每个级别双向扫描各 \(2n-1\) 个字符，时间为 \(O(n\min(n,K))\) ，也可写为 \(O(nK)\) ；空间为 \(O(n+K)\) . 这一界在本题的机器字模型下成立，因为每个长度为 \(j\) 的块都能放入一个整数。

需要注意单节点环、全部字符相同、跨越编号边界、\(K>n\) 、以及不同回文块相邻但不相同的情况。最大乘积不超过 \(nK\) ，参考程序使用 32 位无符号数维护位窗口，使用整数保存长度与异或结果。

验证穷举了长度不超过 8 的全部二进制环，再以直接截取、反转比较和逐块比较核对随机环。正式数据含百万字符的全同串、交替串、回文周期串、破坏一个位置的近周期串等。性能测量见评测环境与性能。

魔法面包 题解¶