No.027 D

石 $i$ に戻る組み合わせの数の方がわかりやすい. この数を $C(i)$ とすると,

$$C(i) = \sum_{j=1}^{h_i} C(i+j)$$

となるからである.

これを $10 \times 10$ のコンパニオン行列として表せば, 任意の区間の値を求めるのは行列の積を計算することになり, 総乗を計算するセグメントツリーに入れておけば $O(\log N)$ で計算できる.

…のだが, メモリが足りない.

そこで, クエリを先読みして座標圧縮する. 使われることのない座標はまとめて先に計算しておけばメモリ節約ができる.