置换环模板题E - Permute K times 2
输入样本 1
6 3
5 6 3 1 2 4
样本输出 1
6 1 3 2 4 5
每次操作后, P P P 都会发生如下变化:
- 第一次操作后, P P P 为 ( 2 , 4 , 3 , 5 , 6 , 1 ) (2,4,3,5,6,1) (2,4,3,5,6,1) 。
- 第二次操作后, P P P 为 ( 4 , 5 , 3 , 6 , 1 , 2 ) (4,5,3,6,1,2) (4,5,3,6,1,2) 。
- 第三次运算后, P P P 为 ( 6 , 1 , 3 , 2 , 4 , 5 ) (6,1,3,2,4,5) (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;
}