No.766 金魚すくい

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 35
作問者 : ei1333ei1333 / テスター : treeonetreeone
0 ProblemId : 2321 / 出題時の順位表

問題文

水槽に金魚が $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. 金魚 $1$ をすくおうとして, ポイが破れる(確率 $\frac 1 2$)。
  2. 金魚 $1$ をすくう。次に金魚 $2$ をすくおうとして, ポイが破れる(確率 $\frac 1 4)$。
  3. 金魚 $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
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。