この問題は、 ダブリング と呼ばれるテクニックで解くことができます。

ダブリングに関する参考資料をいくつか挙げます。

• ダブリングの基本概念とその応用
• [競プロ用]ダブリングまとめ
• 【競技プログラミング】ダブリングまとめ

まず、 \(k=0,1,\dots,59\) について、以下のような配列 \(P_k\) を求めることを考えます。

• \(P_{k,i} :=\) ( \(2^k\) 回操作をしたとき、操作後の数列の \(i\) 番目には操作前の \(P_{k,i}\) 番目の要素が入っている)

まず、 \(P_0 = X\) とできます。
さらに、 \(P_{k-1}\) から \(P_k\) を以下のように求めることができます。

• \(P_{k,i} = P_{k-1}[P_{k-1,i}]\)

直感的には、「 \(2^{k-1}\) 回の操作」に相当する操作を \(2\) 回かければ 「 \(2^k\) 回の操作」に相当する操作が得られます。

より一般には、操作 \(l\) 回に相当する列 \(L\) と操作 \(r\) 回に相当する列 \(R\) について、 \(T_i=R[L_i]\) とすれば操作 \(l+r\) 回に相当する列 \(T\) が得られます。これを「操作の合成」と呼ぶことにします。

これらの列 \(P_i\) から「 \(K\) 回操作をしたとき、操作後の数列の \(i\) 番目には操作前の \(Q_i\) 番目の要素が入っている」という数列 \(Q\) を求めることができればこの問題を解くことができます。どのようにすればよいでしょうか。

これは、繰り返し二乗法に似た要領で実現可能です。具体的には、以下の通りに求められます。

• \(Q=(1,2,\dots,N)\) とする (操作 \(0\) 回に相当します)。
• \(i=0,1,\dots,59\) まで次を繰り返す。
  • もし \(K\) を \(2\) で割った余りが \(1\) なら \(Q\) と \(P_i\) とを合成する。
  • その後、 \(K\) を \(2\) で割る(小数点以下切り捨て)。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  long long k;
  cin >> n >> k;
  vector<vector<int>> p(60,vector<int>(n+1));
  for(int i=1;i<=n;i++){
    cin >> p[0][i];
  }
  vector<int> a(n+1);
  for(int i=1;i<=n;i++){
    cin >> a[i];
  }
  for(int lv=1;lv<60;lv++){
    for(int i=1;i<=n;i++){
      p[lv][i]=p[lv-1][p[lv-1][i]];
    }
  }
  vector<int> q(n+1);
  for(int i=1;i<=n;i++){q[i]=i;}
  for(int lv=0;lv<60;lv++){
    if(k%2){
      for(int i=1;i<=n;i++){
        q[i]=p[lv][q[i]];
      }
    }
    k/=2;
  }
  for(int i=1;i<=n;i++){
    if(i>=2){cout << " ";}
    cout << a[q[i]];
  }cout << "\n";
  return 0;
}