题意简述
- 构造一个长度为 \(n\) 的排列 \(A\),使得对于任意的 \(l,r\)( \(1 \le l < r \le n\))都满足 \(A_l+A_{l+1}+⋯+A_r\) 不可以被 \(r-l+1\) 整除。
- 输出其中一种合法排列即可。
解题思路
构造题。考虑对 \(n\) 进行分类讨论:
- 当 \(n = 1\) 时,由样例即可得合法排列为 \(1\)。
- 当 \(n\) 为大于 \(1\) 的奇数时,因为 \(n-1\) 和 \(n+1\) 必然能被 \(2\) 整除,故不论 \(A\) 如何排列,只需取 \(l=1,r=n\),必有
被 \(r-l+1=n\) 整除。故程序输出 \(-1\)。
- 当 \(n\) 为偶数时,先猜后证。
先猜测构造方案:
首先,取 \(l=i,r=i+1\)(其中 \(1 \le i \le n-1\)),则
\[\begin{aligned} A_l+A_{l+1}+⋯+A_r &= A_i+A_{i+1} \end{aligned}\]如果 \(A_i,A_i+1\) 同奇偶,则上式为偶数,有可能会被 \(n\) 整除。
所以 \(A_i,A_i+1\) 奇偶性不同(其中 \(1 \le i \le n-1\))。
其次,取 \(l=i,r=i+2\)(其中 \(1 \le i \le n-2\)),则
\[\begin{aligned} A_l+A_{l+1}+⋯+A_r &= A_i+A_{i+1}+A_{i+2} \end{aligned}\]同理分析可得排列 \(A\) 不能出现 \(3\) 个连续的数字。
综上所述,一种合法的排列 \(A\) 必须满足以下两点:
- 相邻的两个数奇偶性不同。
- 不能出现 \(3\) 个连续的数字。
则猜测答案为形如 \(2,1,4,3,⋯,n,n-1\) 的排列。
再证明其正确性:
考虑分类讨论 \(l,r\) 的奇偶性异同:
- 当 \(l,r\) 的奇偶性不同时,不妨 \(l\) 为奇数,\(r\) 为偶数,则
因为 \(l+r\) 为奇数,则\(\frac{l+r }{2}\)一定不是整数,那么\(S_{l,r}\)一定不被 \(r-l+1\) 整除。
- 当 \(l,r\) 的奇偶性相同时,则
与上一种情况相反,因为 \(l+r\) 为偶数,则\(\frac{l+r }{2}\)是整数,那么\((r-l+1)\times (\frac{l+r }{2})\)被 \(r-l+1\) 整除。
则所求 \(S_{l,r}\) 不被 \(r-l+1\) 整除。
证毕!
代码实现
很简单,就不放了