JAG Summer Camp 2017 Day 1 C - すごろく

• 問題
• AC

まずは$B_i$がすべて$0$であるような問題を考える。ループがない、つまり同じマスに二回止まることがないので、ゴール以前の各マスに止まる確率を足し合わせたものが求める期待値になっている。

$p(i) =$ サイコロを振って$i$が書かれた面が出る確率 $\operatorname{dp}[x] =$マス$x$に止まる確率

とするとき、0-basedで考えると遷移は

$\operatorname{dp}[x] = \sum_{0 \le k \le x}\operatorname{dp}[x-k]p(k)$

となって、これはオンラインFFTで解ける形になっている。

$B_i$が必ずしも0でない場合について考える。$B_x > 0$であるようなマス$x$については、オンラインFFT中に$\operatorname{dp}[x]$に加算する時に、代わりに$\operatorname{dp}[x+B_x]$に加算すればよい。また、$B_x < 0$、つまり休みのマスについては、そのようなマスに止まる確率$\times |B_x|$を結果に足せばよさそう……だが、他のマスから$B$の影響で進んできた場合は休まないので、$\operatorname{dp}$を構成し終えてから$\operatorname{dp}[x] \times |B_x|$を後で足すと正しく計算できない。やはりオンラインFFT中に$\operatorname{dp}[x]$に加算する瞬間に結果に足す必要がある。