有 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)，然而没跑过上种做法。