自动搬运

查看原文

来自洛谷，原作者为

	Cocoly1990 成事不说 遂事不谏 既往不咎

搬运于2025-08-24 22:37:03，当前版本为作者最后更新于2022-03-22 18:35:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

验题人题解。

引理一：定义 $f_x=n-x+1$.

则无论如何置换，$\left(x,y\right)$ 上的数只能置换到

$$\left(x,y\right),\left(f_x,y\right),\left(x,f_y\right),\left(f_x,f_y\right) $$

上。

证明：易证。

---

引理二：我们称上述四个位置为一个置换环。

数据有解当且仅当四个位置的值是

$$x,x,f_x,f_x$$

证明：也易证。

---

考虑对于每个环分情况构造。

一个很重要的原则是构造的时候每一行必须翻转偶数次，即不能影响行内其他的值。

---

Case 1：

$$\begin{matrix} x & f_x \\ x & f_x \end{matrix}$$

已经归位，无需构造。

---

Case 2：对角线换位

$$\begin{matrix} f_x & x \\ x & f_x \end{matrix}$$

交换第二列。

$$\begin{matrix} f_x & f_x \\ x & x \end{matrix}$$

交换第一行。

$$\begin{matrix} f_x & f_x \\ x & x \end{matrix}$$

交换第二列。

$$\begin{matrix} f_x & x \\ x & f_x \end{matrix}$$

交换第一行。

$$\begin{matrix} x & f_x \\ x & f_x \end{matrix}$$

done.

---

Case 3：双侧换位

$$\begin{matrix} f_x & x \\ f_x & x \end{matrix}$$

交换第一行。

$$\begin{matrix} x & f_x \\ f_x & x \end{matrix}$$

交换第一列。

$$\begin{matrix} f_x & f_x \\ x & x \end{matrix}$$

交换第二列。

$$\begin{matrix} f_x & x \\ x & f_x \end{matrix}$$

交换第一行。

$$\begin{matrix} x & f_x \\ x & f_x \end{matrix}$$

done.