No.766 金魚すくい
レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 66
作問者 :
ei1333333
/ テスター :
treeone
タグ : / 解いたユーザー数 66
作問者 :
ei1333333
/ テスター :
treeone
問題文最終更新日: 2018-12-13 23:38:55
問題文
水槽に金魚が $N$ 匹います。それぞれの金魚には $1$ から $N$ までの番号が振られていて, 金魚 $i$ の価値は $V_i$ です。
あなたはポイと呼ばれる金魚をすくう道具を $M$ 個持っています。 魚をポイですくおうとすると $P$ ％の確率で破れ, $100-P$ ％の確率ですくえます。 一度破れたポイをもう一度使うことはできません。
あなたはすべての金魚をすくい終わるか, すべてのポイが破れるまで以下の行動を続けます。
- まだ破れていないポイで, まだすくえていない好きな金魚をすくおうとする。
あなたはすくった金魚の価値の和の期待値が最大になるように行動します。 このとき, この期待値は常に既約分数 $\frac A B$ の形で表すことができます。 $B$ の $\pmod {10^9 + 7}$ での逆元を $B^{−1}$ として, $A \times B^{-1} \pmod {10^9 + 7}$ を求めてください。
入力
$N$ $M$ $P$ $V_1$ $V_2$ ... $V_N$
- $1 \leq N \leq 10^5$
- $1 \leq M \leq 10^5$
- $0 \leq P \leq 100$
- $1 \leq V_i \leq 10^9$
- 入力はすべて整数
出力
$1$ 行に答えを出力せよ。
サンプル
サンプル1
入力
2 1 50 100 50
出力
500000066
最初に金魚 $1$ をすくおうとするのが最適です。このとき以下の $3$ 通りの行動が考えられます。
- 金魚 $1$ をすくおうとして, ポイが破れる(確率 $\frac 1 2$)。
- 金魚 $1$ をすくう。次に金魚 $2$ をすくおうとして, ポイが破れる(確率 $\frac 1 4)$。
- 金魚 $1$ をすくう。次に金魚 $2$ をすくう(確率 $\frac 1 4$)。
期待値は $0 \frac 1 2 + 100 \frac 1 4 + 150 \frac 1 4 = \frac {125} 2$ です。$2$ の $\pmod {10^9 + 7}$ での逆元は $5 \times 10^8 + 4$ なので, $125 \times (5 \times 10^8+4) \pmod {10^9+7} = 500000066$ を出力します。
サンプル2
入力
1 100 99 100
出力
977688169
サンプル3
入力
4 1 0 3 1000 30 300
出力
1333
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。