题解：P12910 [NERC 2020] King's Task

qryqwq · 2025-06-23 11:40:39 · 题解

提供一种线性的做法。

首先对于 n\bmod2=0 的做法是简单的，感性理解一下，将这个排列分为前半段和后半段。在执行操作 2 的时候，都是在同一段内交换，所以前后并不会影响。故最终只会有 [1,2,3,\dots,2n]、[n+1,n+2,n+3,\dots,2n,1,2,3,\dots,n]、[2,1,4,3,6,5,\dots,2n,2n-1]、[n+2,n+1,n+4,n+3,n+6,n+5\dots,2n,2n-1,2,1,4,3,6,5,\dots,n,n-1] 这四种情况有解，需进行的操作数分别为 0、1、1、2，打个表应该很容易理解。

若 n\bmod2=1，有一个很显然的结论就是执行完操作 2 后必须执行操作 1，执行完操作 1 后必须执行操作 2。所以操作方案可以分为以下四种情况：

• 第一次执行操作 1，最后一次执行操作 1。
• 第一次执行操作 2，最后一次执行操作 1。
• 第一次执行操作 1，最后一次执行操作 2。
• 第一次执行操作 2，最后一次执行操作 2。

这四种情况其实可以变为两种情况，根据操作数的奇偶性来决定。所以可以从排列有序开始，暴力计算 n 在排列中的下标，而 n 在排列中的下标一定是不同的。因为若存在两个有解的排列且 n 在这两个排列中的下标相同同，根据 n\bmod2=0 的方法，将这个排列拆成前后两个部分可以证明这两个排列一定相同。
所以直接模拟 n 的下标，若 n 的下标和排列中的相同，则记录下当前的操作次数。将操作 2 开始的情况和操作 1 开始的情况各模拟一遍即可。
难点就来到了判无解，由于排列的置换满足结合律，所以可以用快速幂解决。或者把排列拆分成多个环，依次操作每个环。若最后与排列相同则有解。