Yukicoder No.1013 〇マス進む
ダブリングの練習。
まず「次の場所 % n」の値をダブリングテーブルを前処理しておく。
for (int i = 1; i < m; i ++) {
for (int j = 0; j < n ; J++) {
table[i][j] = table[i-1][table[i-1][j]]
}
}
ダブリングテーブル自体はこんな感じで更新できる。
さらにp[i]進んだときに何周するかがわかれば良い。
これもダブリングと同じようにマスjから2^(i-1)だけ進んだときに何周したか、というのをテーブルで書いておく
for (int i = 1; i < m; i ++) {
for (int j = 0; j < n ; J++) {
table2[i][j] = table[i-1][j] + table2[i-1][table[i-1][j]]
}
}
位置のダブリングテーブルを使うとこんな感じでかける。最後に「周回数 * n + 位置」をそれぞれのクエリにO(log(K)) で計算する。
全体計算量はO(N log(K))
