金魚は価値が高いものから狙うのが最適なのは明らかであるので, \(V_i\) は降順でソートしておく.

格子状になっている道路を仮定し, 最初は原点にいるとする. 金魚をすくえたら右に移動し, ポイが破れたら上に移動する. こうすることで, \((n, m)\) 地点にいるということは \(n\) 匹の金魚を \(m\) 個のポイを使ってすくったことになる.

このとき, 最終的にたどり着く点は \((N, m) \ (0 \leq m \leq M-1)\) か \((n, M) \ (0 \leq n \leq N-1)\) である.

\((N, m)\) にたどりつく確率は \((N-1, m)\) にたどりついて次にすくう確率であり, 価値の和はすべての金魚の価値を足したものになるので, このときの期待値は

\[\left( \sum_{i=1}^N V_i \right) {}_{N-1+m}C_m (1-p)^N p^m\]

となる.

また \((n, M)\) にたどりついたときも同様にその期待値は

\[\left( \sum_{i=1}^n V_i \right) {}_{n+M-1}C_m (1-p)^n p^M\]

となる. ともに \(p = P/100\) である.

これらを \(n, m\) について計算して足し合わせればいい. 和の部分は累積和を計算しておき, べき乗, 階乗およびその逆元もあらかじめ計算しておけるので, 計算量は \(O(N+M)\) である.

なお, 規約分数と書かれているが, \(kA(kB)^{-1} = AB^{-1}\) となるので約分の必要はない.