P15651 题解

zjy2008 · 2026-03-07 23:32:39 · 题解

首先发现，对于一次操作，可以被分解为：将序列 shift 一个位置 或者 把相邻两个位置合并。所以一个 b 中元素一点对应于 a 中的一个循环区间。

不妨假设这个区间为 [1,l] 我们发现，若 l>4，那么可以 112 把 l 减少 3。所以本质不同的区间长度只有 1,2,3,4。且对于长度 3 的区间是不能完成合并的。

接下来有一个非常有想象力的操作，考虑把长度为 2 的区间 i 变成一条 i\leftrightarrow i+1 的无向边，长度为 4 的则变成两条。走过一条无向边相当于把最左侧从起点变为终点。那么我们实际上就是要从 a 中最左侧的区间走一条欧拉路径到 b 中最左侧的区间。对于欧拉路径的判定，我们只需要记录第 1 个区间到第 i 个区间的连通性，第 i 个区间度数的奇偶性即可。

于是我们可以写出一个 dp，dp_{k,l,r,0/1/2,0/1,0/1} 表示已经确定 b_{1\sim k} 对应到 a_{l\sim r}，现在 b_{k+1} 已经连的边数，是否经过 a' 的最左侧，现在 1 和 k+1 是否联通。注意 a' 是 a 进行一些操作使得不存在跨过 n\to 1 区间的新序列，所以需要对一开始跨过 n\to 1 的区间进行一些特殊的处理。

容易发现这个 dp 只记录了 0/1，把 l 放进 bitset 可以把时间复杂度除以 w。

注意到需要枚举 b_i = \oplus_{i=l}^r a_i，显然可以只需要一个区间取所有可行区间，其他只需要取在 \mod 3 相等意义下长度最小的（如果跨过 n\to 1 可能需要 \mod 6）。

综上可以做到时间复杂度 O(\dfrac{n^3}w)。

特别难写的代码。