P12676 题解

经验分享区
1

n=1

若 m=1 构造 [1] 即可满足条件。
若 m>1，每个数出现的位置都不相同且只出现一次，故无解。

n\bmod2=0

直接循环交替构造，即构造 [1,2,3,\dots,m],[m,m-1,m-2,\dots,1],\dots,[m,m-1,m-2,\dots,1]。i 在相邻两个数组的下标中分别为 i 和 m-i+1，其总和为 m+1，是个定值。故该构造满足条件。

n>1\wedge n\bmod2=1

m\bmod2=0

所有下标的和为 \dfrac{nm(m+1)}{2}。由于有 m 个数，每个数的下标之和为 \dfrac{n(m+1)}{2}。若 n\bmod2=1 且 m\bmod2=0 则 n(m+1) 为奇数，除不尽，没有满足条件的构造方式。

m\bmod2=1

对于前 n-3 组，可以套用 n\bmod2=0 时的构造方式。其全部数的下标和相同。所以问题转化为 n=3 时如何构造。
对于 n=3 时的情况，可以考虑先构造前两组，再通过 \dfrac{n(m+1)}{2} 减去 i 在前两个数组中的下标和形成最后一个数组。问题便转化为如何构造前两个数组，才能使 \dfrac{n(m+1)}{2} 减去 i 在前两个数组中的下标互不相同，构成一个排列。
考虑以下构造，第一行按顺序输出，即构造 [1,2,3,\dots,m]。第二行将后 \dfrac{m+1}{2} 个数提前。i 在第一个数组中的下标为 i，在第二个数组中，若 i\le\dfrac{m-1}{2}，则在数组中的下标为 i+\dfrac{m+1}{2}，否则在数组中的下标为 i-\dfrac{m-1}{2}。
下面分情况讨论，对于第一种情况，

\begin{aligned} \dfrac{3(m+1)}{2}-i-(i+\dfrac{m+1}{2})&=\dfrac{3(m+1)}{2}-2i-\dfrac{m+1}{2}\\&=\dfrac{2(m+1)}{2}-2i\\&=m+1-2i \end{aligned}

对于第二种情况，

\begin{aligned} \dfrac{3(m+1)}{2}-i-(i-\dfrac{m-1}{2})&=\dfrac{3(m+1)}{2}-2i+\dfrac{m-1}{2}\\&=\dfrac{3(m+1)}{2}-2i-\dfrac{m+1}{2}-1\\&=\dfrac{2(m+1)}{2}-2i-1\\&=m+1-2i-1\\&=m-2i \end{aligned}

注意到第一种情况的位置必定为奇数，第二中情况的位置必定为偶数，所以它们不可能相同。对于每种情况，因为 i 的值不同，所以它们的值也一定不相同。故构造出来的所有数都不相同，构成一个排列。

通过代码。

2

不是所以这 Markdown 咋调