ダブリング

[tipstar0125]

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_be https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ed

[tipstar0125]

tessoku-book A57

input! {
    N: usize,
    Q: usize,
    A: [Usize1; N],
    XY: [(Usize1, usize); Q]
}

let mut dp = vec![vec![0_usize; N]; 30];
dp[0] = A;

for i in 1..30 {
    for j in 0..N {
        dp[i][j] = dp[i - 1][dp[i - 1][j]];
    }
}

for &(x, y) in &XY {
    let mut pos = x;
    for i in (0..30).rev() {
        if y & (1 << i) > 0 {
            pos = dp[i][pos];
        }
    }
    println!("{}", pos + 1);
}

[tipstar0125]

• 各始点から1回分だけ遷移したときの状態を求める
• 各始点について、ダブリングにより2^k分だけ遷移した時の状態を前計算
• 試行回数Kを2進数で表現した時に、bitが立っている箇所を逆回しで辿る