yukicoder No.995 → 問題リンク
数学的な解法と行列累乗を使う解法がある。今回は前者。
解法
$p/q$ といちいち言うのは面倒なので、以降は $r=p/q$ とする。
実際の実装でも、$p/q$ をなんらかの変数に入れておくと楽に実装できるだろう。
タピオカは確率 $r$ で移動し、$1-r$ で移動しないので、反復試行の確率により、タピオカが $i$ 回移動する確率は$$P_i:={}_K\mathrm{C}_ir^i(1-r)^{K-i}$$である。
最初からミルクティーに入っていたタピオカが最終的にミルクティーの中にいる確率は、タピオカが偶数回移動した場合なので、$P$ の偶数番目の項の和となる。
数式できちんと書くと$$\displaystyle\sum_{i=0}^{\lfloor K/2 \rfloor}P_{2i}$$である。
ここで、二項定理より$$\bigl((1-r)+r\bigr)^K=\sum_{i=0}^K P_i \tag{1}$$$$\bigl((1-r)-r\bigr)^K=\sum_{i=0}^K (-1)^iP_i\tag{2}$$が成り立つ。
$(1)$ と $(2)$ を足し合わせると、奇数番目の項は+と-で打ち消し合い、偶数番目の項だけが2倍された形で残る。
また、$(1)$ の左辺は $1$ であり、$(2)$ の左辺は $(1-2r)^K$ である。
よって、最初からミルクティーに入っていたタピオカが最終的にミルクティーの中にいる確率は$$\frac12\bigl(1+(1-2r)^K\bigr)$$となる。
最初はキッチンにあったタピオカが最終的にミルクティーの中にいる確率は、タピオカが奇数回移動した場合なので、$P$ の奇数番目の項の和となる。
今度は $(1)$ から $(2)$ を引くと、偶数番目の項は打ち消し合い、奇数番目の項だけが2倍された形で残る。
よって、最初はキッチンにあったタピオカが最終的にミルクティーの中にいる確率は$$\frac12\bigl(1-(1-2r)^K\bigr)$$となる。
期待値は (美味しさ) $\times$ (ミルクティーに入る確率) なので、求める答えは$$(\ b\ の先頭\ M\ 項の和\ )\times\frac12\bigl(1+(1-2r)^K\bigr)+(\ b\ の末尾\ N-M\ 項の和\ )\times\frac12\bigl(1-(1-2r)^K\bigr)$$
となる。$K$ 乗を求めるには繰り返し二乗法を使えばよい。