自动搬运

查看原文

来自洛谷，原作者为

	HyB_Capricornus 黄梅时节家家A，青草池塘处处WA，有WA不A过夜半，闲切红题冒火花

搬运于2025-08-24 22:46:08，当前版本为作者最后更新于2023-04-05 22:28:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

还没有人发题解，我来一发。

Sol

设原序列为 $B$。

令操作 $C$ 为将 $B_{A_1}$ 挪至 $B_{A_2}$，将 $B_{A_2}$ 挪至 $B_{A_3}$，$\ldots$，将 $B_{A_n}$ 挪至 $B_{A_1}$。

令操作 $-x$ 为将序列逆时针转 $x$ 次，即 $B_1 \to B_2$，$B_2 \to B_3$，$\ldots$，$B_n \to B_1$。

令操作 $+x$ 为将序列顺时针转 $x$ 次。

重点来了：

我们可以把将 $A$ 向后挪再进行 $C$ 操作想成先将 $B$ 逆时针转 $1$ 次，然后进行 $C$ 操作，然后再顺时针转回去

当然每次转的次数不同，例如进行两次将 $A$ 向后挪再进行 $C$ 操作，我们就需要逆时针转 $2$ 次，然后进行 $C$ 操作，然后再顺时针转回去

则操作为：

其中 $+$ 与 $-$ 可以抵消，抵消后结果为：

我们称 $C,-1$ 为 $D$ 操作

我们创建数组 $jmp[i][j]$，其中 $jmp[i][j]=d$ 表示进行 $2^j$ 次 $D$ 操作把 $b_i$ 挪到了 $d$ 位置。

通过倍增，原始暴力的复杂度 $O(nT)$ 成功优化到 $O(n\log_{2}{T})$，复杂度显然可以通过本题。

最后不要忘了顺时针转 $n$ 次，这道题目就做出来了。

代码

一些忠告：

1. 最后不要忘了顺时针转 $n$ 次。
2. 本人代码 $31$ 行，$y$ 很大，需要取模，否则会变成负数(赛时被卡)。
3. 请不要抄题解。