P8880 题解
Xy_top
·
·
题解
构造题看着就头晕，其实这题还是很简单的。
首先来考虑一下不能构造的情况：
无论给你的排列怎么打乱，它的和都不变，所以我们利用等差数列公式求出它的和为：
题目中又说让我们用两个排列构造，那么这两个排列的数字和就是 $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$，符合题意。然后就是一个桶存一下就完的事儿。
代码很简单：
```cpp
#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;
}
```