自动搬运

查看原文

来自洛谷，原作者为

	ezoixx130 浴乎沂，风乎舞雩，咏而归

搬运于2025-08-24 22:07:41，当前版本为作者最后更新于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]);
}