题解 P5151 【HKE与他的小朋友】
ezoixx130
2019-01-12 15:29:21
这不是快速幂模板题吗。。。为什么题解里是倍增，强连通分量，tarjan？？？
题意就是给你一个置换$P$，求$P^k$。
直接快速幂就好了啊。
时间复杂度$O(nlogk)$
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010
int n,k,p[MAXN],tmp[MAXN],ans[MAXN];
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)scanf("%d",p+i),ans[i]=i;
while(k)
{
if(k&1)
{
for(int i=1;i<=n;++i)tmp[i]=ans[p[i]];
for(int i=1;i<=n;++i)ans[i]=tmp[i];
}
for(int i=1;i<=n;++i)tmp[i]=p[p[i]];
for(int i=1;i<=n;++i)p[i]=tmp[i];
k>>=1;
}
for(int i=1;i<=n;++i)tmp[ans[i]]=i;
for(int i=1;i<=n;++i)printf("%d ",tmp[i]);
}
```