ダブリングとは
本番ではABC167Dの問題を周期性を利用して解いたがダブリングでも解けるらしいので、Pythonでダブリング書いてみました。ダブリング自体初めて知りました。
ダブリングはdoublingというテーブルを用意してdoubling[i]に2^i移動した時のインデックスをn個分格納するというもの。
今回の場合、kが10^18なのに計算量が間に合うのはすごい。
コード
n, k = list(map(int, input().split()))
a = [i - 1 for i in list(map(int, input().split()))]
logk = k.bit_length()
doubling = [[-1 for _ in range(n)] for _ in range(logk)]
for i in range(n):
doubling[0][i] = a[i]
for i in range(1, logk):
for j in range(n):
doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]
index = 0
k_bin = list(map(int, [list(bin(k))[-i] for i in range(1, logk + 1)]))
for i in range(logk):
if k_bin[i]:
index = doubling[i][index]
print(index + 1)
最後のkを2進数に変換してint型のリストにしているk_binはだいぶ頭が悪い書き方をしているとは自覚しているので、今まで避けてきたBit演算を勉強してもっときれいに書けるようにしたい。