P8221 [WFOI - 02] I wanna reverse to reserve（翻转）
Cocoly1990
·
·
题解
验题人题解。
引理一：定义 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：
x & f_x \\
x & f_x
\end{matrix}
已经归位，无需构造。
Case 2：对角线换位
f_x & x \\
x & f_x
\end{matrix}
交换第二列。
f_x & f_x \\
x & x
\end{matrix}
交换第一行。
f_x & f_x \\
x & x
\end{matrix}
交换第二列。
f_x & x \\
x & f_x
\end{matrix}
交换第一行。
x & f_x \\
x & f_x
\end{matrix}
done.
Case 3：双侧换位
f_x & x \\
f_x & x
\end{matrix}
交换第一行。
x & f_x \\
f_x & x
\end{matrix}
交换第一列。
f_x & f_x \\
x & x
\end{matrix}
交换第二列。
f_x & x \\
x & f_x
\end{matrix}
交换第一行。
x & f_x \\
x & f_x
\end{matrix}
done.