盒子与球：题解

思路

设目标排列为 $b$，并令

$d_i$ 表示跨过分界线 $i$ 需要向右净运送多少个球。把一个球移动一格恰好跨过一个分界线，所以从 $a$ 变成 $b$ 的最少操作数为

目标必须满足 $d_n=0$，即球数不变。若最少需要 $D$ 步，则可以把任意一次移动立刻反向来额外增加两步；状态图又是二分图，所以恰好 $k$ 步可达当且仅当 $D\le k$ 且 $D\equiv k\pmod2$。

扫描位置 $i$ 时枚举目标位 $b_i\in\{0,1\}$，前缀差转移为 $d_i=d_{i-1}+a_i-b_i$，代价增加 $|d_i|$。最终统计前缀差为零、代价不超过 $k$ 且与 $k$ 同奇偶的方案。

若某时刻 $|d|=x$，到达该差至少已经累计 $1+2+\cdots+x$ 的代价。因此只需保留满足 $x(x+1)/2\le k$ 的前缀差，范围为 $O(\sqrt k)$。

做法

• 子任务 1：把排列编码为二进制状态，逐步 BFS/集合转移恰好 $k$ 层。
• 子任务 2：保留全部 $[-n,n]$ 前缀差，做 $O(n^2k)$ 动态规划。
• 子任务 3：用三角下界把前缀差裁剪到 $O(\sqrt k)$，复杂度 $O(nk\sqrt k)$。

正确性证明

引理 1：$D(a,b)=\sum_i|d_i|$ 是把 $a$ 变成 $b$ 的最少移动次数。

每次相邻移动只跨过一个分界线，而分界线 $i$ 的净跨越次数至少为 $|d_i|$，故任何方案至少需要该和。按球的相对顺序匹配初始和目标位置，可恰好完成这些净跨越，所以下界可达。

引理 2：目标 $b$ 恰好 $k$ 步可达当且仅当 $D(a,b)\le k$ 且二者同奇偶。

必要性由最短路下界和每次相邻交换改变排列逆序奇偶性得到。充分性方面，先走一条长度 $D$ 的最短路；因始终既有球又有空盒，可在任意合法移动后立即反向，每次增加两步，直至长度为 $k$。

引理 3：动态规划恰好计数所有满足条件的目标排列。

每个位置独立选择目标位零或一，转移唯一确定新的前缀差并累加 $|d_i|$。最终差为零等价于球数相同；由引理 2，筛选代价和奇偶性后恰为全部可达目标。

定理：算法输出恰好 $k$ 次操作后可能的不同排列数。

由引理 3，DP 与可达目标排列一一对应且无重计，故求和结果正确。

复杂度

时间复杂度 $O(nk\sqrt k)$，空间复杂度 $O(k\sqrt k)$。