题解：P12356 「HCOI-R2」Rabbit Panic (Hard Ver.)

验题人题解（？过了半年才写。

建议降蓝。。

先特判 $n=1$ 操作 $0$ 次、$m=1$ 无解。

然后对于 $m$ 为偶数，容易想到一个显然的构造且能顶到次数的理论下限，从两侧开始每次分别对称地选择一段，最后多余的选择之前操作过的不会影响平均数。

对于 $m$ 为奇数，$n$ 为偶数时最终平均数需要是 $\frac{n+1}2$，而无论进行什么操作，得出的数都一定是 $\frac{p}{m^k},p\in\mathbb{N^+},k\in\mathbb{N}$ 的形式，所以一定无解。

都是奇数时，如果沿用以上的做法每次操作时都把 $\lceil{\frac{n}2}\rceil$ 选上，达不到理论下限且事实上确实不够优。

考虑手玩 $m=3$ 找规律输出方案。

类似于 1 5 6，2 3 7 的我们可以花费两次操作完成 $6$ 个。以 $n=6k+1,k\in \mathbb{N_+}$ 的情况为例，$i$、$3k+i+1$、$6k-2i+2$ 和 $k+i$、$2k+i$、$6k-2i+3$ 都能得到 $3k+1$，且没有重复。

那么除 $\lceil{\frac{n}2}\rceil$ 外最后会剩下 $2$ 个或者 $4$ 个，可以一开始预留出两边对称的 $2$ 个或者 $4$ 个，这样最后也是选他们中对称的两个和 $\lceil{\frac{n}2}\rceil$ 一起。虽然会有重复操作但一定能顶到理论下限 $\lceil\frac{n-1}3\rceil$。

发现 $m>3$ 可以用多余的 $m-3$（偶数）个位置把左右最边上的部分对称消掉，于是做完了。