行き先がN個あり、それぞれの要素について1回移動した時の移動先が決まっているとする。

このとき K回の移動を繰り返した時の到達点を高速に求める手法 のひとつにダブリングがある。

計算量

この場合愚直に計算しようとするとK回の移動をそのままシミュレートするので、計算量はO(K)となる。

が、ダブリングを用いることでO(N log K)とすることができる。なぜO(N log K)となるかは後の具体的な方法を知れば理解できる。

方法

dpに似ていて、あらかじめ計算結果のテーブルを用意しておく。このとき用意するテーブルは、穴iから2j回移動した場合の行き先をシミュレートする

すなわち、N個の場所に対して、Kを2で割った回数分計算が必要なので、テーブル作成に必要な計算量はO(N log K)となる

実際に答えを求める際にはKを2進数で表記し、右シフトしながらjを取り最下位1ビットが1であれば今いる位置を更新していくことで解を出すことができる。

例題: ABC141 D

D - Teleporter

この問題は先の例よりも易しい。というのは、場所iからの移動先は何回かすると同じ場所を通り始めるからだ。なので周期を見つけられればダブリングを知らなくとも解ける。ただ、今回はダブリングを使って解く。そのためのテーブルは log2 1018 = 59.79470... の前計算を行えばよい。

僕は以下のように実装した。

n,k=map(int,input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

dp=[[0 for _ in range(n)] for _ in range(60)]

for i in range(60):
  for j in range(n):
    if i==0:
      dp[i][j]=a[j]
    else:
      dp[i][j]=dp[i-1][dp[i-1][j]]

ans=0
now=0
while k:
  if k&1:
    ans=dp[now][ans]
  now+=1
  k>>=1

print(ans+1)

ミソはk&1で、これは下位1bitが1であればtrueとなる。あとはk>>=1で右に1bitずつシフトしていく。