题解：P12356 「HCOI-R2」Rabbit Panic
IvanZhang2009
·
·
题解
这个题两三年前出出来的时候还是我做出来的。
翻了一下之前的题解。
除了 n,m 都是奇数的情况都是简单的，直接去看 easy version 的题解即可。
不妨仅考虑 m=3。对于 m>3 的情况，我们仿照 m 是偶数的情况，我们对中间的区间求解 m=3，然后在每次操作都加入 \frac{m-3}{2} 对 i 和 n-i+1 即可。
我们需要把 $1\sim(6x+1)$ 的所有数除了 $3x+1$ 分成 $2x$ 组，每组有三个数，且和都相等。我的思路是将这些数先分成三组：$[1,2x]$ 的数分为第一组，$[4x+2,6x+1]$ 分为第三组，剩下的是第二组。可以构造出每个三元组的三个数分别选自三个组的方案。
列出限制 $a\in [1,2x],b\in[2x+1,4x+1],c\in[4x+2,6x+1],b\neq 3x+1,a+b+c=9x+3$。
稍加变化得到：$a\in [-x+1,x],b\in[-x,x],c\in[-x,x-1],b\neq 0,a+b+c=0$。（这一步只需要把 $a,b,c$ 各自减掉一个常数）
把 $b,c$ 取反得到：$a,c\in[-x+1,x],b\in[-x,x],b\neq 0,a-c=b$。
这个形式就很好看了。这相当于我们要求一个长度为 $2x$ 的排列 $p_{1\dots 2x}$ 使得 $p_i-i$ 恰好是 $\pm [1,x]$ 的所有数。
手玩一下可以发现 $2,4,6,\dots,2x,1,3,5,\dots 2x-1$ 恰好符合条件。那么做完了。
代码找不到了。