解説とは違う方法なので 問題 N個の石があって，i番目の石はi+1..i+H\[i\]にジャンプ出来る． 次のD個のクエリに答えたい：s番目の石からt番目の石へ移動する方法の数を答えよ． キーワード 行列演算表現を用いた動的計画法 行列が乗ったセグメントツリー

タイトルについて 正しくは「データアクセスに制限のある Binary Indexed Tree (と同じクエリに答えるデータ構造) の高速化」です Binary Indexed Tree とは 以下のクエリに時間O(logN)で答えることが出来るデータ構造． 初期化 サイズNの配列の要素を0に初…

解説と若干違っていたので 概要 https://beta.atcoder.jp/contests/arc061/tasks/arc061_c 鉄道会社の乗り換えを最小化せよ かなり雑なブログ記事です