题解 P5151 【HKE与他的小朋友】

ezoixx130 · 2019-01-12 15:29:21 · 题解

这不是快速幂模板题吗。。。为什么题解里是倍增，强连通分量，tarjan？？？

题意就是给你一个置换P，求P^k。

直接快速幂就好了啊。

时间复杂度O(nlogk)

代码：

#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]);
}