Permute K times

本文主要是介绍Permute K times，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：Permute K times

首先我们考虑暴力的作法，就是将一个点走k步，最后所在的那个点即为所求，考虑数据范围显然不可以，因此我们可以采用倍增的写法去实现。每个点的步数转化成二进制形式去求，用st表。

代码：

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5+5;
int n,k;
int a[N],b[N];
int f[N][105];void solve(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>f[i][0];}for(int i=1;i<=n;i++){cin>>a[i];b[i] = i;}for(int j=1;j<=63;j++){for(int i=1;i<=n;i++){f[i][j] = f[f[i][j-1]][j-1];}}int t = 0;while(k){if(k&1){for(int i=1;i<=n;i++){b[i] = f[b[i]][t];}}t++;k>>=1;}for(int i=1;i<=n;i++)cout<<a[b[i]]<<" ";cout<<"\n";}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T=1;while(T--){solve();}return 0;
}

这篇关于Permute K times的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---