# 魔法面包 题解

解法贡献：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 的全部二进制环，再以直接截取、反转比较和逐块比较核对随机环。正式数据含百万字符的全同串、交替串、回文周期串、破坏一个位置的近周期串等。性能测量见[评测环境与性能](../../../docs/评测环境与性能.md)。