[AtCoder] ABC 167 D – Teleporter

問題

方針

配列は \( 0 \) を基準として考えます。

閉路を構築する問題です。頂点 \( 1 \) から出発してループになっている道を見つけるには、頂点に訪れた回数を数えれば良いです。\( 2 \) 回以上訪れた頂点の集合がループとなります。配列 \( v\) を探索で訪れた順の頂点の集合、 配列 \( l \) を閉路の頂点の集合とします。初期値は、\( v_0 = 1\)、\( v_1 = A_0\)、\( |v| = 2\) です。

\( |l| \leq |v| \) は明らかです。\( 3 \) 回訪れた頂点が出てきた時点で探索を打ち切ります。

\( K < |v| \) のとき

このとき、\( v_{K} \) が答えとなります。

\( |v| \leq K\) のとき

このとき、頂点 \( l_0 \) に \( 2 \) 回目に訪れるたときのテレポーターを使った回数は、\( |v| \) です。閉路は周期が \( |l| \) なので、答えは、

\[l_{(K – |v|) \bmod |l|}\]

となります。

コード