本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-17 09:19:32

模拟赛搬这个题，过于困难，拼尽全力无法战胜。

题意

有 $n$ 个球和 $n$ 个盒，编号均为 $1$ 到 $n$，初始可任意将球放到盒内。要求对 $i$ 从 $1$ 到 $n$ 依次操作，每次拿出 $i$ 盒内的球并任意排列成 $p_k$，之后同时将所有 $p_j$ 球放到 $p_{j+1\bmod k}$ 盒中。给出最终每个球所在盒的编号 $a_i$，判断是否可能出现该最终局面。多组数据，$\sum n\le 2.5\times 10^5$。

题解

发现顺序操作时自由度太高了，初值和过程中的排列顺序均难以确定，于是考虑倒着做，这样初始状态确定了。将状态用图表示，即球编号 $i$ 向所在盒编号 $a_i$ 连边，形成基环树森林。则对 $i$ 操作时所有指向 $i$ 的点均断开，再以任意顺序连成一个环；倒过来考虑时即找到一个环，将其断开并全部指向 $i$。

注意到上述两操作并不等价，原因是前者要求取所有指向 $i$ 的点，而后者没有限制这一点。仔细思考后发现只有两种情况合法，分别是 $i$ 点入度为 $0$ 或 $i$ 点在环上且入度为 $1$。前者可任意选环操作，后者必须选 $i$ 点所在的环，这对应操作前 $a_i=i$ 形成自环，会将其操作后环上前驱代表的球留在 $i$ 盒内。

于是出现了新的自由度：$i$ 点不在环上时可任意选环。猜想选 $i$ 所在连通块的环最优，手推发现选其他环时，除 $i$ 点外所有点的可操作性均不变；选所在连通块的环时，$i$ 点到环路径上入度只比限制多 $1$ 的点由不可操作变为可操作，其余点仍不变，于是这可能使局面变得更可操作，一定是最优的。

于是有了一个确定过程：从初始 $(i,a_i)$ 形成的图开始，倒序操作所有 $i$。每次先检查入度是否合法，不合法则无解；否则找到该连通块内的环，将其断开并全部指向 $i$，过程中修改入度。若能进行完 $n$ 次操作则有解。直接模拟该过程，暴力跳后继找环，复杂度可证明不超过 $O(n\sqrt n)$，事实上跑得特别快，证明如下（By Kevin090228）：

每次操作遍历操作点到环路径上和环上的所有点。由于路径上的点在操作后会变到环上，只分析每次操作环长 $L$ 的总和即可，即复杂度为 $O(\sum L)$。设局面 $S$ 的势能 $V(S)=\sum r_i^2$，即所有点入度的平方和。操作会使环上点的入度减 $1$，势能减小 $\sum_{t\in C} r_t^2-(r_t-1)^2=\sum_{t\in C} 2r_t-1$，由于全局入度和为 $n$，这是不超过 $2n$ 的；同时操作点 $x$ 入度增加环长 $L$，势能增加 $(r_x+L)^2-r_x^2=2Lr_x+L^2$，这是不低于 $L^2$ 的。

由于势能 $V(S)$ 上界为 $n^2$ 且 $n$ 次操作总减小量不超过 $2n^2$，总增加量一定不超过 $3n^2$。忽略 $2Lr_x$ 这一项，有 $\sum L^2\le 3n^2$，根据柯西不等式可得 $\sum L$ 至多是 $n\sqrt n$ 级别的，于是复杂度 $O(\sum L)$ 不超过 $O(n\sqrt n)$。

还有另一种做法，考虑进一步刻画合法局面，注意到操作点 $i$ 时要求 $i$ 没有环外入度，因此对于 $i$ 点不在环上的前子树 $u$，若其所有点编号均小于 $i$，则 $i$ 点操作前该子树不变，$i$ 点会由于 $(u,i)$ 存在而无法操作，必然无解。于是对于每个点 $i$，其每个子树 $u$ 最大值 $w_u$ 均需满足 $w_u\gt i$，才有可能有解，这是一个必要条件。

至于充分性，感性理解若满足条件，则每个子树内都有点操作过，从而 $(u,i)$ 这条边曾被纳入环中，不再构成限制，因此 $i$ 点此时可以操作，不太会严格证明。总之这个条件是充要的，据此可判断合法性，DFS 即可找出环并求出所有 $w_u$，时间复杂度 $O(n)$，然而没跑过上种做法。