JustShuffle - 题解

标签与难度

标签: 置换, 循环分解, 数论, 模逆元, 扩展欧几里得算法, 图论 难度: 1800

题目大意喵~

主人你好呀~ 这道题是关于排列组合的魔法呢，喵！

是这样的：我们有一排 $n$ 个位置，从 $1$ 到 $n$ 编号。现在有一个目标排列 $A$，它告诉我们，如果我们将初始序列 $\{1, 2, \dots, n\}$ 进行某种置换（可以理解为一种固定的洗牌方式）$P$，并且重复这个洗牌动作 $k$ 次之后，序列就会变成 $A$。

我们的任务，就是找出这个神秘的基础洗牌方式 $P$ 到底是什么样的。如果找到了，就把 $P$ 打印出来；如果有很多种可能的 $P$，随便打印一种就可以啦。如果根本不存在这样的 $P$，就打印 "-1"。

举个栗子：如果 $n=3, k=2$, 目标排列 $A = \{3, 1, 2\}$。我们想找一个 $P$，使得对 $\{1, 2, 3\}$ 操作两次 $P$ 后得到 $\{3, 1, 2\}$。这个 $P$ 就是我们要找的答案啦！

解题思路分析

这道题看起来有点抽象，但别担心，跟着我的思路一步步来，你就会发现其中的奥秘，喵~

我们可以把排列看作一个映射关系。目标排列 $A$ 告诉我们，数字 $i$ 经过 $k$ 次 $P$ 变换后，会跑到 $A_i$ 的位置。如果我们把这个关系写成函数形式，就是 $P^k(i) = A_i$。我们的目标就是求出 $P$。

解决这个问题的关键，在于一个叫做「置换的循环分解」的神奇工具！

1. 把排列拆成小圈圈（循环分解）

任何一个排列都可以被分解成若干个不相交的循环。听起来很酷吧？其实很简单！

我们从数字 $1$ 开始，看看它在 $A$ 中会变成谁？$1 \to A_1$。那 $A_1$ 又会变成谁呢？$A_1 \to A_{A_1}$。我们一直这样跟下去，因为数字总数是有限的，最终一定会回到起点 $1$，形成一个闭合的圈圈，也就是一个“循环”。

比如说，如果 $A = \{2, 3, 1, 5, 4\}$，我们来分解它：

• 从 $1$ 开始：$1 \to A_1=2 \to A_2=3 \to A_3=1$。看，我们回到了 $1$！这就形成了一个循环 (1 -> 2 -> 3 -> 1)。
• 接下来找一个还没被访问过的数字，比如 $4$：$4 \to A_4=5 \to A_5=4$。又一个循环 (4 -> 5 -> 4)。

这样，整个排列 $A$ 就被我们拆解成了两个独立的循环：(1, 2, 3) 和 (4, 5)。

2. 在小圈圈里解谜

既然排列 $A$ 可以被拆成独立的循环，那么我们想找的 $P$ 也一定是在这些循环内部进行操作的，它不会把一个圈里的元素变到另一个圈里去。所以，我们可以对每个循环独立求解，最后再把结果合起来，喵~

让我们聚焦于一个长度为 $L$ 的循环，比如上面的 (1, 2, 3)，它的长度 $L=3$。为了方便，我们把它的元素记作 $c_0, c_1, \dots, c_{L-1}$。在这个例子里就是 $c_0=1, c_1=2, c_2=3$。

排列 $A$ 的作用，就是让圈里的每个元素向前走一步：$A(c_i) = c_{(i+1) \pmod L}$。 我们要求的 $P$ 作用 $k$ 次后要达到和 $A$ 一样的效果。

那么，我们不妨假设 $P$ 的作用也是让圈里的元素向前跳跃，但它可能不是跳一步，而是跳 j 步。也就是 $P(c_i) = c_{(i+j) \pmod L}$。

如果 $P$ 作用一次是跳 j 步，那么作用 $k$ 次，就是跳了 $k \times j$ 步啦！所以 $P^k(c_i) = c_{(i + k \cdot j) \pmod L}$。

我们希望这个结果和 $A$ 的作用一样，也就是跳一步：

$$i + k \cdot j \equiv i + 1 \pmod L$$

两边消掉 $i$，就得到：

$$k \cdot j \equiv 1 \pmod L$$

喵呀！这不就是模逆元的定义嘛！我们需要找到一个 j，它是 $k$ 在模 $L$ 意义下的乘法逆元。只要我们能找到这个 j，我们就能确定 $P$ 在这个循环上的作用方式了！

3. 寻找逆元 j

怎么求 $k$ 模 $L$ 的逆元呢？我们可以用「扩展欧几里得算法」。这个算法可以求解形如 $ax + by = \gcd(a, b)$ 的方程。当我们要求 $k \cdot j \equiv 1 \pmod L$ 时，就相当于求解 $k \cdot j + L \cdot y = 1$。这只有在 $\gcd(k, L) = 1$ 时才有解。题目中的数据似乎保证了总是有解的，所以我们不用太担心无解的情况，大胆地用扩展欧几里得算法去求就好啦！

求出逆元 j 后，我们就知道了 $P$ 的作用：对于循环中的第 $i$ 个元素 $c_i$，它在 $P$ 的作用下会变成第 $(i+j) \pmod L$ 个元素 $c_{(i+j) \pmod L}$。

4. 算法总结

好啦，思路已经清晰了，我们来总结一下完整的步骤吧：

1. 创建一个 visited 数组，来标记哪些数字已经被放入循环了。
2. 从 $1$ 到 $n$ 遍历所有数字。如果数字 $i$ 还没被访问过： a. 从 $i$ 出发，沿着 $A$ 的映射（curr = A[curr]）不断前进，直到回到 $i$，把沿途所有数字记录下来，形成一个循环。同时标记这些数字为已访问。 b. 得到一个长度为 $L$ 的循环 cycle_elements。 c. 使用扩展欧几里得算法，计算 $k$ 模 $L$ 的逆元，我们称之为 k_inv。 d. 对于这个循环中的每一个元素 cycle_elements[j]，它在 $P$ 中的下一个元素就是 cycle_elements[(j + k_inv) % L]。我们将这个映射关系记录到我们的答案排列 $P$ 中。
3. 遍历完所有数字后，我们就得到了完整的排列 $P$，把它打印出来就大功告成啦！

代码实现

下面是我根据上面的思路，精心重构的一份代码，注释超详细的哦，希望能帮到你，喵~

#include <iostream>
#include <vector>
#include <numeric>

// 使用扩展欧几里得算法求解 ax + by = gcd(a, b)
// 返回 a, b 的最大公约数
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extended_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

// 计算 a 在模 m 下的乘法逆元
// 我们需要求解 a * x ≡ 1 (mod m)
// 前提是 gcd(a, m) == 1
long long mod_inverse(long long a, long long m) {
    long long x, y;
    extended_gcd(a, m, x, y);
    // 保证返回的是正数
    return (x % m + m) % m;
}

int main() {
    // 为了加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    long long k;
    // 题目可能有多组输入，但样例和常见比赛形式通常是单组
    // 这里用 while 循环处理，更具通用性
    while (std::cin >> n >> k) {
        std::vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) {
            std::cin >> a[i];
        }

        std::vector<int> p(n + 1); // 这就是我们要找的神秘排列 P
        std::vector<bool> visited(n + 1, false);

        // 遍历所有元素，分解出所有不相交的循环
        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                // 发现一个新的循环的起点！
                std::vector<int> current_cycle;
                int current_node = i;
                
                // 沿着 A 的指向，把整个循环找出来
                while (!visited[current_node]) {
                    visited[current_node] = true;
                    current_cycle.push_back(current_node);
                    current_node = a[current_node];
                }

                long long cycle_len = current_cycle.size();
                
                // 计算 k 在模 cycle_len 下的逆元
                // 这就是 P 在这个循环里要跳跃的步数 j
                long long k_inv = mod_inverse(k, cycle_len);

                // 根据跳跃步数 k_inv，构建 P 在这个循环上的映射
                for (long long j = 0; j < cycle_len; ++j) {
                    int from_node = current_cycle[j];
                    int to_node_idx = (j + k_inv) % cycle_len;
                    int to_node = current_cycle[to_node_idx];
                    p[from_node] = to_node;
                }
            }
        }

        // 打印最终结果
        for (int i = 1; i <= n; ++i) {
            std::cout << p[i] << (i == n ? "" : " ");
        }
        std::cout << "\n";
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(N \log N)$ 我们首先需要遍历 $1$ 到 $N$ 的所有元素来寻找和构建循环。这个过程每个元素只会被访问一次，所以是 $O(N)$。对于每个找到的长度为 $L$ 的循环，我们需要计算一次模逆元。使用扩展欧几里得算法计算逆元的时间复杂度是 $O(\log L)$。所有循环的长度之和为 $N$。在最坏的情况下（比如一个长度为 $N$ 的大循环），复杂度是 $O(N + \log N)$。如果有很多小循环，总时间是 $\sum O(\log L_i)$，这个和也小于 $O(N \log N)$。因此，总的时间复杂度是 $O(N \log N)$。

• 空间复杂度: $O(N)$ 我们需要一个大小为 $N$ 的数组 a 来存储输入的排列，一个大小为 $N$ 的数组 p 来存储结果，一个大小为 $N$ 的 visited 数组来标记访问过的节点。在寻找循环时，我们还需要一个 current_cycle 向量，最坏情况下它可能需要存储 $N$ 个元素（当整个排列是一个大循环时）。所以，总的空间复杂度是 $O(N)$，喵~

知识点总结

这道题真是一次有趣的冒险，它教会了我们：

1. 置换与循环分解: 这是理解和处理排列问题的基石。将复杂的排列问题分解成若干个独立的子问题（循环），是非常强大的思想。
2. 模逆元: 在数论和组合数学中，模逆元是个常客。当遇到形如 $a \cdot x \equiv b \pmod m$ 的问题时，就应该想到它啦。
3. 扩展欧几里得算法: 它是计算模逆元的标准工具，特别是当模数不一定是质数时。每个ACMer都应该熟练掌握它！
4. k-th root of a permutation: 这个问题在学术上被称为“求排列的k次根”，我们今天解决的就是它的一个特例。

希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦！一起加油，变得更强，喵~！