解法0: 周期性を用いる
\(i \rightarrow a[i]\) と遷移を繰り返すと，あるところでサイクルに入る． \(i_{0}\)からスタートするとして， \[ i_{0} \rightarrow \cdots a \rightarrow b \rightarrow \cdots \rightarrow c \rightarrow a \rightarrow \cdots \] の形となる． サイクルの部分の長さを調べれば，そのサイクル部分を減らせるので， 最悪で\(O(N)\)のシュミレーションで解ける．
解法1: ダブリング
こちらはテンプレ通りなので機械的にできる． \(2^{i}, i \in \mathbb{N}\) 回移動したときの 移動先を前計算しておけば， 指数を2進数展開すれば \(O(log E)\), \(E\)は指数 で求まる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// cycle
int main() {
ll n, k;
cin >> n >> k;
vll a(n); rep(i,n) { cin >> a[i]; a[i]--; }
vll ord(n, -1);
ll cyc_len, cyc_v;
{
ll i = 0;
ll cnt = 0;
while(ord[i]==-1){
ord[i] = cnt++;
i = a[i];
}
cyc_len = cnt-ord[i];
cyc_v = i;
}
ll r;
{
ll cnt = 0;
ll i = 0;
while(i != cyc_v){
cnt++;
i = a[i];
}
r = cnt;
}
{
if(k >= r) k = r + (k-r)%cyc_len;
ll i = 0;
rep(_,k){
i = a[i];
}
cout << i+1 << endl;
}
return 0;
}
// doubling
int main() {
ll n,k;
cin >> n >> k;
vll a(n); rep(i,n) { cin >> a[i]; a[i]--; }
vvll dp(63, vll(n));
rep(i,n) dp[0][i] = a[i];
rep(j,62) rep(i,n) dp[j+1][i] = dp[j][ dp[j][i] ];
ll j = 0;
ll i = 0;
while(k){
if(k&1){
i = dp[j][i];
}
k >>= 1;
j++;
}
cout << i+1 << endl;
return 0;
}
