ABC189 F - Sugoroku2 (600)
コンテスト中の考察
iマス目にスタート地点から到着するまでの回数の期待値を$ f(i) とすると$ f(i) = \sum_{j=1}^{m}\frac{f(i-j)}{m} + 1 (振り出しに戻るマスは足さない)
$ f(0) は$ 振り出しに戻るマスのfの和+1になる
$ f(0) = Xと置くと、$ f(i) = aX+bの形で表せるので一次方程式を解けば解けそう
Xの方とそうでないほうでそれぞれセグ木を用いて計算した
サンプル3が合わず
解説の方法
振り出しに戻るマス以外でiマス目からNマス目に到着するまでの回数の期待値を$ f(i) とすると$ f(i) = \sum_{j=1}^{m}\frac{f(i+j)}{m} + 1
$ f(0) = Xと置くと、振り出しマスでは$ f(i) = X
同様に一次方程式を解けば解ける
Nマスでセグ木にそれぞれ触るので$ O(N \log M)