[ABC377E] Permute K times 2 题解

FFTotoro · 2024-10-28 17:36:49 · 题解

考虑 K=1 时，同时进行 P_i\leftarrow P_{P_i} 相当于进行一次排列复合 P\leftarrow P\circ P；如果 K=2，就是 P\leftarrow (P\circ P)\circ(P\circ P)，由于 \circ 具有结合律，定义 P^k 为 k 个 P 依次复合形成的结果 \begin{matrix}\underbrace{P\circ P\circ\cdots\circ P}\\k\end{matrix}，则上面的结果等价于 P^4……以此类推，走 K 步的结果就是 P^{2^K}。

考虑建图，连边 i\to P_i(1\le i\le N)，可以见得最终的图是一些环。于是把每个环找出来，答案就相当于从 i 开始走 2^K 步走到的位置。由于 2^K 很大，我们将其对环长取模之后进行处理：这一部分可以使用快速幂解决。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int qpow(int a,int b,int m){
  int r=1;
  while(b){
    if(b&1)(r*=a)%=m;
    (a*=a)%=m,b>>=1;
  }
  return r;
}
main(){
  ios::sync_with_stdio(false);
  int n,k; cin>>n>>k;
  vector<int> p(n),r(n);
  for(auto &i:p)cin>>i,i--;
  vector<bool> b(n);
  for(int i=0;i<n;i++)
    if(!b[i]){
      vector<int> v;
      for(int x=i;!b[x];x=p[x])
        b[x]=true,v.emplace_back(x);
      int d=qpow(2,k,v.size());
      for(int i=0;i<v.size();i++)
        r[v[i]]=v[(i+d)%v.size()];
    }
  for(int i:r)cout<<i+1<<' ';
  cout<<endl;
  return 0;
}