C. Combination Lock 详细题解

一、问题重述

构造一个长度为 $n$ 的排列 $p_1, p_2, \dots, p_n$（数字 $1$ 到 $n$ 各出现一次），使得对于每一个循环移位，恰好有一个位置 $i$ 满足该位置上的值等于其位置编号。

输出任意一个满足条件的排列；如果不存在，输出 $-1$。

---

二、核心推导

2.1 数学转化

将排列下标从 $0$ 开始考虑（$0 \le i \le n-1$），设 $p_i$ 为下标 $i$ 处的值（$1 \le p_i \le n$）。

一个循环移位相当于将数组向右移动 $k$ 位（$k = 0, 1, \dots, n-1$）。原下标 $i$ 在移位后的新下标为 $(i + k) \bmod n$。

“恰好有一个固定点”意味着：对于每个 $k$，存在唯一的 $i$ 使得：

$$(i + k) \bmod n = p_i - 1 \quad \text{(值域从 0 开始)}$$

记 $q_i = p_i - 1 \in [0, n-1]$，则条件为：

$$(i + k) \bmod n = q_i$$

整理得：

$$k \equiv q_i - i \pmod{n}$$

对于固定的 $k$，由 $i$ 唯一确定。因此映射 $k \mapsto i$ 是双射。故 $\{q_i - i \bmod n \mid i = 0,\dots,n-1\}$ 必须恰好是 $\{0,1,\dots,n-1\}$。

2.2 必要条件

对全体 $i$ 求和：

$$\sum_{i=0}^{n-1} (q_i - i) \equiv \sum_{k=0}^{n-1} k \pmod{n} $$

左边：

$$\sum q_i - \sum i = \frac{n(n-1)}{2} - \frac{n(n-1)}{2} = 0 $$

右边：

$$\sum_{k=0}^{n-1} k = \frac{n(n-1)}{2}$$

因此：

$$\frac{n(n-1)}{2} \equiv 0 \pmod{n}$$

即 $n \cdot \frac{n-1}{2} \equiv 0 \pmod{n}$，等价于 $\frac{n-1}{2}$ 为整数？不对，检查：

$\frac{n(n-1)}{2} \bmod n = 0$ 当且仅当 $n$ 是奇数。因为 $n(n-1)/2 = n \cdot (n-1)/2$，$n$ 整除该项当且仅当 $(n-1)/2$ 是整数，即 $n$ 为奇数。

结论：当 $n$ 为偶数时无解，输出 $-1$。

---

三、构造方案（$n$ 为奇数）

当 $n$ 为奇数时，一个简单的构造是：

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

即降序排列。

验证：将 $p$ 转换为 $0$-基 $q_i = (n - i) \bmod n$？实际 $p_i = n - i$（$i$ 从 $1$ 开始），$q_i = n - i - 1$。计算 $q_i - i$：

$$q_i - i = (n - i - 1) - i = n - 2i - 1 \pmod{n}$$

当 $i$ 取 $0,1,\dots,n-1$ 时，$n - 2i - 1 \bmod n$ 遍历所有 $n$ 个不同值（因为 $n$ 奇数，$2$ 可逆）。因此每个 $k$ 恰好对应一个 $i$。

---

四、标程代码

#include <iostream>
using namespace std;

void solve() {
    int n;
    cin >> n;
    if (n % 2 == 0) {
        cout << -1 << endl;
        return;
    }
    for (int i = n; i > 0; i--) {
        cout << i << " \n"[i == 1];
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

五、示例验证

示例 1：$n = 4$（偶数）

输出 -1 ✅

示例 2：$n = 5$

输出 5 4 3 2 1，检查各循环移位（$0$‑基）：

• 移位 0：4 3 2 1 0 → 固定点：下标 4（值 0）? 等，需要仔细。 实际上原例输出是 4 1 3 5 2，说明不唯一。本题只要任意解，降序也可行。

示例 3：$n = 3$

输出 3 2 1，循环移位：

• 3 2 1：固定点？值=位置？3 在位置 1 不等，2 在位置 2 等，1 在位置 3 不等 → 1 个固定点
• 1 3 2：1=位置1，3≠2，2=位置3？位置3 值是2 → 1 个固定点
• 2 1 3：2≠1，1≠2，3=3 → 1 个固定点 ✅

---

六、复杂度分析

• 每个测试用例 $O(n)$
• 总 $n$ 不超过 $2 \times 10^5$，$t \le 500$，可通过

---

七、总结

条件	结论
$n$ 为偶数	无解，输出 $-1$
$n$ 为奇数	有解，降序排列 $[n, n-1, \dots, 1]$ 是一种构造

核心思想：利用模 $n$ 的线性同余性质，推导出 $n$ 必须为奇数，并给出简单构造。