Teleporter [AtCoder Beginner Contest 167 D]

https://atcoder.jp/contests/abc167/tasks/abc167_d

前提知識

• ダブリング

解説

https://atcoder.jp/contests/abc167/submissions/13093461

初めてこの手の問題に取り組んだ人は、方針にだいぶ迷ったかもしれない。
今回の方針としては、シミュレーションの高速化が方針になる。

愚直にK回の遷移を試すと、最大10¹⁸回なので、それは難しい。
なので、+1+1+1というのをやっていくと間に合わないが、ダブリングという手法を使うと、
+1+2+4のように遷移を行うことができ、シミュレーションを高速化できる。
以下ダブリングを簡単に説明するが、他のサイトで勉強した方が分かりやすいと思う。

ダブリングでは、以下のdpを使う。
dp[p][cu] := 現在頂点cuにいて、そこから2^p回遷移したときの遷移先
最初はもちろんdp[0][cu] = A[cu]からスタートする。
dpの遷移はdp[p][cu] = dp[p-1][ dp[p-1][cu] ]で更新することができる。
これは難しく見えるかもしれないが、
　dp[p-1][cu]で頂点cuから2^p-1回遷移したときの遷移先
であり、
　dp[p-1][ dp[p-1][cu] ]
とすると、これは、そこから更に2^p-1回遷移したときの遷移先となる。
2^p-1 + 2^p-1は2^pなので、2^p回遷移した先を代入することができる。

K=10¹⁸では、2⁶⁰までくらいを作ればいいので、dpは作成することができる。
これを使えば、K回の遷移はビットが立っている部分について、ダブリングのdpテーブルを使って遷移をすればいいので、
シミュレーションを高速化でき、K回後の頂点を答えることができる。

なお、別解として周期性を用いる方法がある。
今回を有向グラフとして考えると、このグラフは有向なもりグラフとなる。
これは、遷移させていくと、ループが1つあることが知られており、ループによる周期性を用いて、
シミュレーションの高速化をすることもできる。
細かな話題

int N; ll K; int A[201010];
int dp[61][201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i], A[i]--;

    rep(cu, 0, N) dp[0][cu] = A[cu];
    rep(p, 1, 61) rep(cu, 0, N) dp[p][cu] = dp[p - 1][dp[p - 1][cu]];

    int cu = 0;
    rrep(p, 60, 0) if (K & (1LL << p)) cu = dp[p][cu];
    cout << cu + 1 << endl;
}