题解

题意简述

给定一个$n$，要求构造一个 $1 \sim n$ 的排列 $p$，使得对于每一个 $i \in [2, n]$ 都有：

$$\max(p_{i-1}, p_i) \bmod i = i-1$$

如果无法构造，输出 $-1$。

---

思路分析

1. 模运算的条件

对于某个固定的 $i$，条件 $\max(p_{i-1}, p_i) \bmod i = i-1$ 等价于：

$$\max(p_{i-1}, p_i) \equiv i-1 \pmod{i}$$

即：

$$\max(p_{i-1}, p_i) = i \cdot k + (i-1) \quad (k \ge 0) $$

由于 $\max(p_{i-1}, p_i) \le n$，并且 $i-1 < i$，所以有两种可能：

• $k = 0$：$\max(p_{i-1}, p_i) = i-1$
• $k \ge 1$：$\max(p_{i-1}, p_i) \ge i + (i-1) = 2i - 1$

但因为排列中元素 $\le n$，当 $i$ 较大时 $k \ge 1$ 会很快不可能。我们需要整体构造。

---

2. 奇数 $n$ 的构造

当 $n$ 为奇数时，我们可以构造：

$$p = [n,\ 1,\ 2,\ 3,\ \dots,\ n-1]$$

验证如下：

• 对于 $i = 2$：

$$\max(p_1, p_2) = \max(n, 1) = n$$

因为 $n$ 是奇数，$n \bmod 2 = 1$，而 $i-1 = 1$，满足条件。

• 对于 $i \ge 3$：

$$\max(p_{i-1}, p_i) = \max(i-2, i-1) = i-1$$

而 $(i-1) \bmod i = i-1$，同样满足。

因此该构造对奇数 $n$ 有效。

---

3. 偶数 $n$ 不可能

我们证明对于偶数 $n$ 不存在这样的排列。

① 位置分析
如果 $n$ 在 $p_1$ 或 $p_2$ 位置：

• 若 $p_1 = n$，则对于 $i=2$，$\max(p_1, p_2) \ge n > n$（不可能，因为最大值就是 $n$？等等，这里逻辑有问题）
  更准确地说，若 $p_1 = n$，则 $\max(p_1, p_2) = n$，要求 $n \bmod 2 = 1$，但偶数$n$ 不满足。
• 若 $p_2 = n$，则对于$i=2$，$\max(p_1, p_2) = n$，同样要求 $n \bmod 2 = 1$，不成立。

所以 $n$ 不能在$p_1$ 或 $p_2$。

若 $p_n = n$，则对于 $i = n$：

$$\max(p_{n-1}, p_n) = \max(p_{n-1}, n) = n$$

要求 $n \bmod n = n-1$，即 $0 = n-1$，不可能。
所以$n$ 也不能在 $p_n$。

因此 $n$ 必须放在 $p_3 \sim p_{n-1}$ 中的某个位置。

② 矛盾推导
设 $x$ 是 $n$ 在排列中的位置（$3 \le x \le n-1$）。

于是：

$$\max(p_{x-1}, p_x) = n$$ $$\max(p_x, p_{x+1}) = n$$

这两个 $i$分别是 $x$ 和 $x+1$。

条件要求：

$$n \bmod x = x-1$$ $$n \bmod (x+1) = x$$

考虑两个相邻整数 $x$ 和$x+1$，它们中必有一个是偶数（因为相邻数一奇一偶）。记这个偶数为 $m$。

那么有：

$$n \bmod m = m-1$$

但 $m-1$ 是奇数，而$n$ 是偶数，偶数模偶数结果应为偶数，不可能得到奇数。矛盾。

因此偶数 $n$ 无解。

---

复杂度

每个测试用例 $O(n)$ 构造输出，总复杂度 $O(\sum n) \le 100 \times 100 = O(10^4)$。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T, n;
    cin >> T;
    while (T--) {
        cin >> n;
        if (n & 1) {                        // n 为奇数
            cout << n << ' ';
            for (int i = 1; i < n; ++i) {
                cout << i << " \n"[i == n - 1];
            }
        } else {                            // n 为偶数
            cout << "-1\n";
        }
    }
    return 0;
}