自动搬运

查看原文

来自洛谷，原作者为

	Xy_top constructive thinking

搬运于2025-08-24 22:43:22，当前版本为作者最后更新于2022-12-04 17:30:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

构造题看着就头晕，其实这题还是很简单的。

首先来考虑一下不能构造的情况：

无论给你的排列怎么打乱，它的和都不变，所以我们利用等差数列公式求出它的和为： $\frac{n\times(n-1)}{2}$。

题目中又说让我们用两个排列构造，那么这两个排列的数字和就是 $n\times(n-1)$。

由题意得这两个东西同余于 $n$，那么相减也同余于 $n$。

即 $\frac{n\times(n-1)}{2}$ 整除 $n$，拆一下变成 $n\times\frac{n-1}{2}$，这时需要分情况讨论。

1：$n$ 为奇数。那么 $n-1$ 为偶数，$\frac{n-1}{2}$ 就是整数，$n$ 再乘以它，自然就是 $n$ 的倍数啦！

2：$n$ 为偶数。那么 $n\times (n-1)$ 就是一奇一偶，相乘得到奇数，除以 $2$ 后不是整数，肯定不是 $n$ 的倍数啦！一定无解。

然后再来考虑 $n$ 为奇数的构造。需要用到一个常用的构造方法：即右（左）移构造。

举个例子， $n=5$。那么构造的方案便是：

0 1 2 3 4
1 2 3 4 0

可以发现，第二行的第 $i$ 个就是第一行的第 $i-1$ 个，下面来证明这种构造方法可以构造出 $0$ ~ $n-1$：

根据同余定理，把右下角的 $0$ 变成 $n$ 不会影响。

然后就会发现每一列相邻两项的和都增加了 $2$，进一步观察发现他都是形如 $2\times i + 1$ 的形式 $(0 \leq i < n)$。

紧接着我们发现当 $2\times i + 1 \leq n$ 时，得到的东西就是 $1,3,...,n$，全是奇数，其中最后一项取模之后得 $0$。

当 $2\times i + 1 > n$ 时，取模完得 $2,4,...,n-1$,全是偶数。

所以这个构造方法构造出来的东西就是 $0$ ~ $n-1$，符合题意。然后就是一个桶存一下就完的事儿。

代码很简单：

#include <iostream>
using namespace std;
int n, a[100010], ans[2][100010];
int main()
{
	cin >> n;
	if (n % 2 == 0)//没有方案的情况
	{
		cout << -1;
		return 0;
	}
	for (int i = 0; i < n; i ++)//预处理 2*i+1的每一项，记录到ans数组中
	{
		ans[0][(2 * i + 1) % n] = i;
		ans[1][(2 * i + 1) % n] = (i + 1) % n;
	}
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 0; i < 2; i ++)//根据a数组每一项的值输出预处理好的答案。
	{
		for (int j = 1; j <= n; j ++) cout << ans[i][a[j] ] << " ";
		cout << \n"";
	}
	return 0;
}