洛谷链接 && AT 链接。

手摸了一个晚上，一天后才敲的代码，最后肚子痛，一只手捂着肚子另一只手把题过了。

思路

令序列为 $\{a_i\}(1 \le i \le n)$。

首先，我们要对样例进行手摸。

例如第一个样例：

原序列为：

$$5 \, 6 \, 3 \, 1 \, 2 \, 4$$

置换依次为：

$$2 \, 4 \, 3 \, 5 \, 6 \, 1 \\ 4 \, 5 \, 3 \, 6 \, 1 \, 2 \\ 6 \, 1 \, 3 \, 2 \, 4 \, 5 \\ 5 \, 6 \, 3 \, 1 \, 2 \, 4$$

我们又回到了原序列。

发现这个序列中，除了 $3$ 以外的元素都会轮番置换。

由小学数学老师教的方法，用笔在当前第 $i$ 数 $a_i$ 与他要到达的第 $a_i$ 个数之间画一个箭头。

由于我们有注意力，我们发现这些箭头形成了一个环。因为序列 $\{a_i\}$ 为排列，不重复，有一个数和另一个数换，最后总有一个数需要顶替这个数的位置，所以成环。

所以这个序列我们就可以看成有 $tot$ 个环，若 $a_i=i$，则这个数看做自环。

于是我们猜想与循环节有关。但是 $n$ 范围较大，会超时。

考虑 $k$ 要怎么处理。继续手摸样例。

我们令第一次置换后序列为 $b_i$，则 $b_i = a_{a_i}$。

令第二次置换后序列为 $c_i$，则 $c_i = b_{b_i} = a_{a_{a_{a_i}}}$。

第三次自行手摸。

容易发现这玩意像套娃一样，每次套的 $a$ 都翻倍，于是得出操作 $k$ 次后会套 $2^k$ 个 $a$。

而对于每个数的套娃，都只会在他所在环上，每套 $1$ 个 $a$ 都表示在换上走一步。不理解的可以手摸。

综上，我们可以得出，对于每个数，置换 $k$ 次后得到的数是这个数在环上走 $2^k$ 步后的数。

于是就可以写代码了，dfs 求环，记录环上每一个数和每个环长度，快速幂计算 $2^k$ 对环长度取模的答案，直接计算每个位置的答案。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define ll long long
vector < int > g[N];
int n, bel[N], pos[N], len[N], ans[N], a[N], tot;
ll k;
map < int, int > hu[N];
bool vis[N];
// _id 是第 _id 个环，dep 没用，本来想用这个记录环长度的
void dfs(int x, int fa, int dep, int _id) {
//	cout << x << " " << fa << endl;
	bel[x] = _id;              // 每个数属于第 _id 个环
	hu[_id][++len[_id]] = x;   // 记录第 _id 个环上每个点，len 是每个环的长度
	pos[x] = len[_id];         // 记录当前第 x 个点在环上的位置
	if (vis[x]) return ;
	vis[x] = 1;   // 标记以访问
	for (int y : g[x])
		if (!vis[y]) dfs(y, x, dep + 1, _id);
}
ll fast_pow(ll base, ll power, ll _p) {
	ll res = 1;
	for (; power; power >>= 1, base = base * base % _p)
		if (power & 1) res = res * base % _p;
	return res % _p;
}
// 快速幂
int main() {
	scanf("%d %lld", &n, &k);
	for (int i = 1; i <= n; ++i) scanf("%d", a + i);
	for (int i = 1; i <= n; ++i) {
		g[i].push_back(a[i]);
		g[a[i]].push_back(i); // 建图（画箭头）
	} 
	for (int i = 1; i <= n; ++i)
		if (!vis[i]) dfs(i, i, 0, ++tot); // tot 表示环的数量
	for (int i = 1; i <= n; ++i) {
		int _p = len[bel[i]];                 // 以长度为模数
		ll bu = fast_pow(2, (ll)k, (ll)_p);   // 在环上走的步数
		int id = (pos[i] + bu) % len[bel[i]]; // 走到第 id 个数
		ans[i] = hu[bel[i]][id ? id : len[bel[i]]];   // 特判取模后变成 0 的情况
	//	cout << _p << " " << bu << endl;
	} 
	for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
	return 0;
}