题目概述

本题要求模拟一个洗牌机的运行过程。洗牌机有 $N$ 个槽位，初始时第 $i$ 张牌放在槽位 $i$ 。洗牌机有一个固定的洗牌函数 $f$ ，它表示在一次洗牌轮次后，原本在槽位 $i$ 的牌会被移动到槽位 $f(i)$ 。现在给定 $N$ 、洗牌轮数 $R$ 以及洗牌函数 $f$ （以排列形式给出），要求输出初始时在槽位 $i$ 的牌在经过 $R$ 轮洗牌后所在的槽位。

输入范围

• $N$ 最多为 $1040$
• $R$ 为 $0\le R<2^{63}$ ，是一个非常大的整数

样例输入

5 0
4 2 1 5 3
5 1
4 2 1 5 3
5 2
4 2 1 5 3

样例输出

1 2 3 4 5
4 2 1 5 3
5 2 4 3 1

---

解题思路分析

1. 问题本质

这个问题本质上是在计算排列的 $R$ 次幂。给定一个排列 $f$ ，我们需要对每个 $i$ （ $1\le i\le N$ ）求出 $f^R(i)$ ，即 $f$ 连续作用 $R$ 次后的结果。

2. 直接模拟的不可行性

由于 $R$ 最大可达 $2^{63}-1$ ，直接模拟 $R$ 次操作显然会超时。我们需要寻找更高效的方法。

3. 利用排列的循环分解性质

任何一个排列都可以唯一分解为若干个不相交的循环（环）。例如，对于排列 $f=[4,2,1,5,3]$ ，我们可以分解为两个环：

• 环 $C_1$ ： $1\to 4\to 5\to 3\to 1$ （长度为 4）
• 环 $C_2$ ： $2\to 2$ （长度为 1）

关键观察 ：在同一个环中，经过 $R$ 次置换等价于在环中向前移动 $R$ 步。由于环是循环的，移动 $R$ 步等价于移动 $R\mathrm{mod}L$ 步，其中 $L$ 是该环的长度。

4. 算法步骤

1. 环分解 ：遍历 $1$ 到 $N$ ，找出所有环，并为每个位置记录：
   • 它属于哪个环（环编号）
   • 它在环中的位置（索引，从 $0$ 开始）
   • 环的长度
2. 计算结果 ：对于每个位置 $i$ ：
   • 找到它所在的环 $C$ ，环长为 $L$
   • 设它在环中的索引为 $p$
   • 则经过 $R$ 轮后，新索引为 $(p+R)\mathrm{mod}L$
   • 从环 $C$ 中取出新索引对应的元素，即为 $f^R(i)$
3. 特判 ：如果 $R=0$ ，则输出原始排列 $1,2,\dots ,N$

5. 时间复杂度

• 环分解： $O(N)$
• 计算结果： $O(N)$
• 总复杂度： $O(N)$ ，可以轻松处理 $N\le 10^4$ 的数据规模

6. 溢出问题注意

$R$ 可能非常大（ $<2^{63}$ ），直接计算 $(p+R)$ 可能溢出 $64$ 位整数。但由于我们只需要 $R\mathrm{mod}L$ ，而 $L\le N\le 1040$ ，因此可以先对 $R$ 取模 $L$ ，再用取模后的值进行计算，避免溢出。

---

代码实现

// Shuffling Cards
// UVa ID: 12642
// Verdict: Accepted
// Submission Date: 2026-01-13
// UVa Run Time: 0.100s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

typedef long long ll;

const int MAXN = 1200;

int n;
int perm[MAXN];        // 原始置换 f
int cur[MAXN];         // 当前置换
int tmp[MAXN];         // 临时数组
int cyclePos[MAXN];    // 每个位置在所属环中的序号（从0开始）
int cycleId[MAXN];     // 每个位置所属环的编号
vector<int> cycles[MAXN]; // 存储每个环的元素
bool visited[MAXN];

// 找出所有环并存储
void decomposeCycles() {
    memset(visited, false, sizeof visited);
    int cid = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            int cur = i;
            while (!visited[cur]) {
                visited[cur] = true;
                cycleId[cur] = cid;
                cyclePos[cur] = cycles[cid].size();
                cycles[cid].push_back(cur);
                cur = perm[cur];
            }
            cid++;
        }
    }
}

int main() {
    ll r;
    while (cin >> n >> r) {
        for (int i = 1; i <= n; i++) cin >> perm[i];
        // 如果 r=0，置换为单位置换
        if (r == 0) {
            for (int i = 1; i <= n; i++) {
                if (i > 1) cout << ' ';
                cout << i;
            }
            cout << '\n';
            continue;
        }
        // 初始化环数组
        for (int i = 0; i < n; i++) cycles[i].clear();
        decomposeCycles();
        // 计算最终位置
        for (int i = 1; i <= n; i++) {
            int cid = cycleId[i];
            int pos = cyclePos[i];
            ll cycleLength = cycles[cid].size();
            int rr = r % cycleLength;
            // 在环中移动 r 步
            int newPos = (pos + rr) % cycleLength;
            int target = cycles[cid][newPos];
            cur[i] = target;
        }
        // 输出结果
        for (int i = 1; i <= n; i++) {
            if (i > 1) cout << ' ';
            cout << cur[i];
        }
        cout << '\n';
    }
    return 0;
}

---

总结

本题的关键在于利用排列的循环分解性质，将 $R$ 次置换转化为在环中的循环移动。通过取模操作，我们避免了直接模拟 $R$ 次操作带来的时间复杂度和溢出风险。这种思想在处理排列幂运算、置换群相关问题中非常常见，是一类经典技巧。

对于 $N\le 1040$ 和 $R<2^{63}$ 的输入范围，本算法能够在 $O(N)$ 时间内高效求解，完全满足题目要求。