Codeforces 题解 - [Codeforces Round 867 (Div. 3)-D. Super-Permutation]
题目描述
A permutation is a sequence \(n\) integers, where each integer from \(1\) to \(n\) appears exactly once. For example, \([1]\), \([3,5,2,1,4]\), \([1,3,2]\) are permutations, while \([2,3,2]\), \([4,3,1]\), \([0]\) are not.
Given a permutation \(a\), we construct(构造) an array \(b\), where \(b_i = (a_1 + a_2 +~\dots~+ a_i) \bmod n\).
A permutation of numbers \([a_1, a_2, \dots, a_n]\) is called a super-permutation if \([b_1 + 1, b_2 + 1, \dots, b_n + 1]\) is also a permutation of length \(n\).
Grisha became interested whether a super-permutation of length \(n\) exists. Help him solve this non-trivial(重要的) problem. Output any super-permutation of length \(n\), if it exists. Otherwise(不然), output \(-1\).
输入格式
The first line contains a single integer \(t\) (\(1 \le t \le 10^4\)) — the number of test cases. The description of the test cases follows.
Each test case consists of a single line containing one integer \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — the length of the desired（希望实现的） permutation.
The sum of \(n\) over all test cases does not exceed \(2 \cdot 10^5\).
输出格式
For each test case, output in a separate line:
- \(n\) integers — a super-permutation of length \(n\), if it exists.
- \(-1\), otherwise.
If there are several suitable permutations, output any of them.
题目大意
构造一个数组A
其中\(b_{i} = (a_{1} + a_2 + \dots + a_i)\bmod n\)
使得数组B和数组A均为1~n的全排列
输入
4
1
2
3
6
输出
1
2 1
-1
6 5 2 3 4 1
解题思路
1
\[b_{i} = (a_{1} + a_2 + \dots + a_i)\bmod n \tag{1} (i \geq 2) \]\[b_{i - 1} = (a_{1} + a_2 + \dots + a_{i - 1})\bmod n \tag{2}(i \geq 2) \]由\((1)-(2)\)可得，
\[b_{i} = (b_{i - 1} + a_{i}) \bmod n \]让数字k代表数字n在a数组排列中的位置，即\(a_k=n\). 当\(k>1\)时，
\[b_k = (b_{k - 1} + a_k) \bmod n = (b_{k - 1} + n) \bmod n = b_{k - 1} \]即
\[b_k = b_{k - 1} \]此时一定不是全排列。则k一定为1，即
\[a_1=n \]则
\[b_1 = 0 \]2
如果\(n\)为奇数，
\[b_{n} = (a_{1} + a_{2} + \dots + a_{n}) \bmod n \]\[b_{n} = (1 + 2 + \dots + n) \bmod m = \frac{n(n+1)}{2} \bmod n = 0 = b_1 \]此时也一定不会是全排列。因此n>1时只有n为偶数有可行方案
3
当n为偶数时，
\[a = [n,~1,~n-2,~3,~n-4,~5,~\dots,~n - 1,~2] \]对应的
\[b = [0,~1,~n-1,~2,~n-2,~3,~n-3,~\dots,~\frac{n}{2}] \]代码实现
#include "bits/stdc++.h"
using namespace std;
void Solution()
{
int n; cin >> n;
if(n == 1) { cout << 1 << '\n'; return; }
if (n & 1) { cout << -1 << '\n'; return; }
for(int i = 1;i <= n;++i)
{
if(i & 1)
{
cout << n - i + 1 << ' ';
}
else
{
cout << i - 1 << ' ';
}
}
cout << '\n';
return;
}//Monotonous
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--)
{
Solution();
}
return 0;
}