置换环模板题E - Permute K times 2

输入样本 1

6 3
5 6 3 1 2 4

样本输出 1

6 1 3 2 4 5

每次操作后， $P$ 都会发生如下变化：

• 第一次操作后， $P$ 为 $(2,4,3,5,6,1)$ 。
• 第二次操作后， $P$ 为 $(4,5,3,6,1,2)$ 。
• 第三次运算后， $P$ 为 $(6,1,3,2,4,5)$ 。

因此，打印 6 1 3 2 4 5。

思路：本题利用了置换环的原理，通过数学归纳法可以得知，每一个环中的每一个元素在变换k次后，最终会变成2 ^ k % len 下标所对应的元素，因此我们可以对每个换进行处理即可

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int M = 1e9 + 7;
const int MOD = 998244353;
typedef long long ll;
typedef pair<ll,ll>PII;
typedef pair<double, double>PDD;int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};ll a[N], b[N];
ll n, k;
//置换环模板题ll qmi(ll a, ll b, ll p)
{ll res = 1;while(b){if(b & 1) res = res * a % p;a = a * a % p;b >>= 1;}return res % p;
}
int main()
{cin >> n >> k;//进行k次for(int i = 1; i <= n; i ++){cin >> a[i];}for(int i = 1; i <= n; i ++){if(b[i])continue;//被遍历过的环就不需要在进行置换了vector<int>v;//存环ll p = i;do{v.push_back(p);p = a[p];//找下一个}while(p != i);ll len = v.size();ll id = qmi(2, k, len);//看看最终停在哪一个位置for(int i = 0; i < len; i ++){b[v[i]] = v[(id + i) % len];}}for(int i = 1; i <= n; i ++){cout << b[i] << " ";}return 0;
}