Day 153-Q4 | 関数グラフ上のダブリング（Binary Lifting）

問題

$N$ 個の頂点（0-indexed）があり、各頂点 $i$ にはちょうど1本の有向辺 $i\to\mathrm{next}[i]$ が張られている（自己ループ・複数頂点でのサイクルを含みうる）。

$Q$ 個のクエリが与えられる。各クエリは整数の組 $(v,K)$ で、「頂点$v$から$\mathrm{next}$を$K$回たどった先の頂点」を答えよ。

入力形式

N
next_0 next_1 ... next_{N-1}
Q
v_1 K_1
:
v_Q K_Q

制約

$1 \le N \le 2\times10^5$

$0 \le \mathrm{next}[i] < N$

$1 \le Q \le 2\times10^5$

$0 \le K_i \le 10^{18}$

入出力例

入力例1

5
1 2 3 4 0
2
0 7
2 1000000000000

出力例1

2
2

概念図：長さ5のサイクルとダブリングテーブル

ヒント（段階的開示）

ヒント1（方向性）

$K$を1回ずつシミュレーションすると$K\le10^{18}$では到底間に合わない。「1歩」「2歩」「4歩」……と2の累乗の歩数だけ先の頂点をあらかじめ計算しておけば、$K$を2進数展開して組み合わせるだけで任意の歩数を高速に求められる。

ヒント2（アプローチ）

$\mathrm{up}[k][v]$を「頂点$v$から$2^k$回移動した先」と定義し、$\mathrm{up}[k][v]=\mathrm{up}[k-1][\mathrm{up}[k-1][v]]$ で前計算（$k=0..60$程度）。クエリ$(v,K)$には$K$をビットごとに見て、立っているビット$k$ごとに$v\leftarrow\mathrm{up}[k][v]$と更新する。

ヒント3（誘導）

LOG = 60
up = [[0] * n for _ in range(LOG)]
up[0] = next_arr[:]
for k in range(1, LOG):
    for v in range(n):
        up[k][v] = up[k - 1][up[k - 1][v]]

def jump(v, K):
    for k in range(LOG):
        if (K >> k) & 1:
            v = up[k][v]
    return v

模範解答 (Python)

import sys


def main():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    next_arr = [int(data[idx + i]) for i in range(n)]
    idx += n
    q = int(data[idx]); idx += 1

    LOG = 61
    up = [next_arr[:]]
    for k in range(1, LOG):
        prev = up[-1]
        cur = [prev[prev[v]] for v in range(n)]
        up.append(cur)

    out = []
    for _ in range(q):
        v = int(data[idx]); k_steps = int(data[idx + 1]); idx += 2
        for k in range(LOG):
            if (k_steps >> k) & 1:
                v = up[k][v]
        out.append(v)

    print('\n'.join(map(str, out)))


main()

Step-by-Step 解説

1関数グラフの構造
$0\to1\to2\to3\to4\to0$の長さ5のサイクル。頂点$v$から$K$歩先は$(v+K)\bmod5$。

2upテーブルの中身
$up[0]=[1,2,3,4,0]$、$up[1]=[2,3,4,0,1]$、$up[2]=[4,0,1,2,3]$。

3クエリ1 (v=0,K=7)
$7=4+2+1$。$0\to1(+1)\to3(+2)\to2(+4)$。$(0+7)\bmod5=2$と一致。

4クエリ2 (v=2,K=10^12)
$10^{12}\bmod5=0$なので理論値$(2+0)\bmod5=2$。ダブリングで$\log_2(10^{12})\approx40$回の定数演算で同じ答えが得られる。

よくあるミス

ミス	原因	正しい書き方
$K$をそのままループでシミュレーション	$K\le10^{18}$に間に合わない	ダブリングで$O(\log K)$に落とす
LOGの上限を小さくしすぎる	$K\le10^{18}$は$2^{60}$程度まで必要	LOG=60〜62の余裕を持つ
`up[k-1][v]+up[k-1][v]`のような数値演算にする	頂点インデックスと歩数を混同	必ず`up[k-1][up[k-1][v]]`
ビット走査の順序を誤解する	処理順序の誤解	下位から走査してvを都度更新すれば正しい
N,LOGの二次元配列でメモリ超過	$N=2\times10^5,\mathrm{LOG}=61$で概算$1.2\times10^7$要素	実際に使う範囲までLOGを絞る、arrayモジュール活用

次のステップ

発展: 「尻尾＋サイクル」の一般ケースでサイクル侵入距離とサイクル長を前計算し、ダブリングなしで$O(1)$答える（Floydの循環検出＋剰余演算）方法と比較する。
次回予告: Aho-Corasickオートマトン（複数パターン同時マッチングの基礎構築）

自己評価

完全理解おおむね理解要復習

Day 153-Q4 — 関数グラフ上のダブリング（Binary Lifting on Functional Graph）

問題