E - Permute K times 2

E - Permute K times 2

思路

这题由于序列P是一个排列，所以将P表示成一个图的时候，这个图将由$m$个环构成

对于每个环上的点来说，第一回合它会移动到距离它为$2$的点上，距离它为$2$的点同时也以相同的方式移动，那么第二回合，它就会移动到距离它为$4$的点上，得出规律，一个点移动$k$回合会移动到距离它为$2^k$的点上，由于是在一个环上移动，所以直接取模环的长度即可

代码

这里直接使用jiangly的代码了，很简洁优美

//来自jiangly
#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;int power(int a, i64 b, int p) {int res = 1;for (; b; b /= 2, a = 1LL * a * a % p) {if (b & 1) {res = 1LL * res * a % p;}}return res;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int N;i64 K;std::cin >> N >> K;std::vector<int> P(N);for (int i = 0; i < N; i++) {std::cin >> P[i];P[i]--;}std::vector<bool> vis(N);for (int i = 0; i < N; i++) {if (vis[i]) {continue;}int j = i;std::vector<int> a;while (!vis[j]) {vis[j] = true;a.push_back(j);j = P[j];}i64 d = power(2, K, a.size());for (int x = 0; x < a.size(); x++) {P[a[x]] = a[(x + d) % a.size()];}}for (int i = 0; i < N; i++) {std::cout << P[i] + 1 << " \n"[i == N - 1];}return 0;
}