Moe's CF Life

Appearance

喵哈~ 各位好呀！我是你们的解题猫娘，今天也要元气满满地解决算法问题哦！这次我们遇到的问题是关于一个神奇的组合锁，它的密码每天都在变，而且规律还挺奇特的呢。让我们一起来看看怎么破解它吧，喵~

题目大意 ​

在一个叫做 "NEIMARK" 的 IT 园区里，有一些超级机密的房间，要进去就得解开一个圆形组合锁。这个锁的密码是一个长度为 nn 的排列（也就是 11 到 nn 这 nn 个数字，每个都只出现一次）。

这个排列有个非常特别的性质：对于它自己以及它的所有循环移位，都恰好只有一个位置上的数字和它的位置编号是相同的。我们把这种情况叫做“不动点”。

举个栗子，如果排列是 (p_1, p_2, p_3)，那么 p_2 = 2 就是一个不动点。

循环移位是什么呢？就是把最后一个元素拿到最前面来。比如 (p_1, p_2, p_3) 的一次循环移位就是 (p_3, p_1, p_2)。一个长度为 nn 的排列，总共有 nn 种不同的循环移位（包括它自己）。

我们的任务就是：给定一个数字 nn，找出任意一个满足这个条件的排列。如果找不到，就输出 -1。

题解方法 ​

这个问题看起来有点绕，又是排列又是循环移位的，但别担心，跟着本猫娘的思路，一步步就能解开谜题啦，喵！

关键条件的转换 ​

首先，我们来把“每个循环移位恰好有一个不动点”这个条件变得更“数学”一点，这样才好分析嘛。

我们用 0-based 索引来思考会更方便哦，也就是位置从 0 到 n-1，数字也是 0 到 n-1。设我们要求的排列是 a = (a_0, a_1, ..., a_{n-1})。

一个排列向左循环移位 k 次，原来在 j 位置的元素 a_j 会跑到 (j-k) mod n 的位置。一个不动点意味着新位置上的值等于新位置的索引。也就是说，在某个新位置 i，有 新排列[i] = i。

那么，在新位置 i 的元素原来是在哪个位置呢？它原来在 (i+k) mod n 这个位置。所以，这个条件就变成了：对于任意的 k（从 0 到 n-1），方程 a_{(i+k) mod n} = i 必须有且仅有一个解 i。

这个方程还是有点复杂呢。我们换个角度！令 j = (i+k) mod n，那么 i = (j-k) mod n。代入上面的方程，就得到 a_j = (j-k) mod n。

这个形式就清爽多啦！它告诉我们，对于每一个 k（从 0 到 n-1），方程 a_j - j ≡ -k (mod n) 必须有且仅有一个解 j。

再仔细看看，-k (mod n) 随着 k 取遍 0, 1, ..., n-1，其结果也正好取遍了 0, 1, ..., n-1 的所有值。所以，这等价于说，d_j = (a_j - j) mod n 这个序列，必须也是 0 到 n-1 的一个排列！

所以，问题被我们转化成：寻找一个 0 到 n-1 的排列 a，使得 d_j = (a_j - j) mod n 也是一个 0 到 n-1 的排列。

偶数 n 的情况 ​

当 n 是偶数时，真的存在这样的排列吗？我们来算一笔账，喵~

如果 a 和 d 都是 0 到 n-1 的排列，那么它们的元素之和应该是相等的： sum(a_j) for j=0..n-1 = sum(d_j) for j=0..n-1 = 0 + 1 + ... + (n-1) = n(n-1)/2

我们又有 d_j ≡ a_j - j (mod n)。把它们全部加起来： sum(d_j) ≡ sum(a_j - j) (mod n)sum(d_j) ≡ sum(a_j) - sum(j) (mod n)

因为 sum(a_j) 和 sum(j) 都是 n(n-1)/2，所以： sum(d_j) ≡ n(n-1)/2 - n(n-1)/2 (mod n)sum(d_j) ≡ 0 (mod n)

这说明 sum(d_j) 必须是 n 的倍数。我们知道 sum(d_j) 的实际值是 n(n-1)/2。所以，n(n-1)/2 必须是 n 的倍数。

  • 如果 n 是 奇数，n-1 是偶数，(n-1)/2 是个整数。n * (n-1)/2 自然是 n 的倍数，没问题！
  • 如果 n 是 偶数，n-1 是奇数，(n-1)/2 不是整数。n(n-1)/2 除以 n 会得到 (n-1)/2，不是整数，所以它不是 n 的倍数。这就产生了矛盾！

所以，当 n 是偶数时，这样的排列根本不存在！我们直接输出 -1 就好啦。

奇数 n 的构造方法 ​

既然偶数不行，那奇数 n 肯定有解咯。我们需要构造一个。

最简单的构造方法就是找一个线性的关系，比如 a_j = (c * j) mod n。 要让 a 是一个排列，需要 gcd(c, n) = 1。 要让 d_j = (a_j - j) mod n = ((c-1) * j) mod n 是一个排列，需要 gcd(c-1, n) = 1。

我们能找到这样的 c 吗？当然可以！最简单的就是 c=2。

  • 当 n 是奇数时，gcd(2, n) = 1，满足第一个条件。
  • c-1 = 1，gcd(1, n) = 1 永远满足。

所以，a_j = (2 * j) mod n 就是一个完美的构造！

现在把它换回题目要求的 1-based 索引：

  • 位置是 i = 1, ..., n
  • 数值是 p_i = 1, ..., n

令 j = i-1，a_j = p_i - 1。 p_i - 1 = a_j = (2 * j) mod n = (2 * (i-1)) mod n 所以，p_i = ((2 * (i-1)) mod n) + 1。

这就是我们的答案啦！对于任何奇数 n，我们都可以用这个公式生成一个满足条件的排列。

举个例子，n=5:

  • i=1: p_1 = (2*0)%5 + 1 = 1
  • i=2: p_2 = (2*1)%5 + 1 = 3
  • i=3: p_3 = (2*2)%5 + 1 = 5
  • i=4: p_4 = (2*3)%5 + 1 = 2
  • i=5: p_5 = (2*4)%5 + 1 = 4 排列是 1 3 5 2 4。

（虽然题目的样例输出是 4 1 3 5 2，但那只是另一个可行的解而已，我们的构造同样是正确的哦！）

题解 ​

下面就是实现这个思路的代码啦，非常简洁明了呢！

cpp
#include <iostream>

void solve() {
    int n;
    // 先把 n 读进来，喵~
    std::cin >> n;

    // 根据我们的分析，如果 n 是偶数，就无解啦
    if (n % 2 == 0) {
        std::cout << -1 << "\n";
        return;
    }

    // 如果 n 是奇数，我们就用那个神奇的公式来构造排列
    // p_i = ((2 * (i-1)) mod n) + 1
    // 我们从 i = 1 循环到 n
    for (int i = 1; i <= n; ++i) {
        // C++ 里的 % 运算符对负数行为不一，但这里 i-1 >= 0，所以没问题
        // 为了防止 2 * (i-1) 溢出 int，用 long long 计算一下比较保险
        long long val = (2LL * (i - 1)) % n;
        // 计算出的 val 是 0-based 的，加 1 变回 1-based
        std::cout << val + 1 << (i == n ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    // 加速一下输入输出，跑得快一点，像猫一样！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // 处理多个测试用例
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点介绍 ​

这道题虽然代码不长，但背后涉及到的数学知识点还挺有趣的，本猫娘来给你梳理一下吧！

  1. 排列 (Permutation)

    • 排列就是把一堆东西（比如数字 1 到 n）按照一定顺序排成一列，每个东西只能用一次，不能重复也不能漏掉。就像 n 只猫猫排队领小鱼干，每只猫猫都有一个位置，不能有两只猫猫挤一个位置，也不能有空位子，喵~

  2. 循环移位 (Cyclic Shift)

    • 想象一个旋转木马，上面坐着一排数字。每次旋转一下，最后一个数字就跑到最前面来了，其他数字都往后挪一个位置。这就是循环移位。它在很多字符串和数组问题里都会出现。

  3. 不动点 (Fixed Point)

    • 一个函数或者一个变换里的“不动点”，指的是经过变换后位置不变的元素。在这道题里，就是一个排列 p 中，满足 p_i = i 的那个元素。

  4. 模运算 (Modular Arithmetic)

    • 模运算，也叫“时钟算术”，是解决各种周期性、循环性问题的神器！a mod n 就是 a 除以 n 的余数。它最大的好处是能把无限的整数世界映射到一个有限的 0 到 n-1 的集合里，非常适合处理像本题这样的循环问题。我们证明偶数 n 无解时，就用到了模运算的性质。

  5. 构造性算法 (Constructive Algorithms)

    • 这类问题不要求你计算一个最优值或是一个简单的数字，而是要求你“构造”一个满足特定条件的复杂对象（比如一个图、一个序列或者一个排列）。解这类题通常需要大胆猜想，寻找规律，然后用数学方法证明你的猜想和构造是正确的。就像我们找到 p_i = ((2 * (i-1)) mod n) + 1 这个规律一样。

好啦，这次的题解就到这里啦！希望本猫娘的讲解对你有帮助哦。下次再见，喵~ (ฅ'ω'ฅ)

Released under the MIT License.

Copyright © 2024-present Moe