LINE Verda プログラミングコンテスト (AtCoder Beginner Contest 263) E - Sugoroku 3 (500)
$ x 番目のマスからゴールするまでの操作回数の期待値$ E_x = \frac{1}{A_x +1} \left( E_x + E_{x+1} + \cdots + E_{x+a_x} \right) + 1
これを式変形すると$ E_x = \frac{A_x+1}{A_x} \left( \frac{1}{A_x +1} \left( E_{x+1} + \cdots + E_{x+a_x} \right) + 1 \right)
愚直に求めると各$ x毎に$ \mathcal{O}(N)になるがBITやセグ木を使うことで$ \mathcal{O}(\log N)にできる