問題一覧 > 通常問題

No.766 Goldfish Scooping

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 70
作問者 : ei1333333 / テスター : treeone
お気に入りにしたユーザー ProblemId : 2321 / 自分の提出
問題文最終更新日: 2018-12-13 23:38:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2018 (順位表) の他の問題:

Problem Statement

There are $N$ goldfish in a tank. The goldfish are numbered from $1$ to $N$, and the value of goldfish $i$ is $V_i$.

You have $M$ goldfish-scooping tools called poi. When you try to scoop a fish with a poi, the poi tears with probability $P$ %, and you scoop the fish with probability $100-P$ %. A poi that has torn once cannot be used again.

You repeat the following action until you have scooped all the goldfish or all the poi have torn.

  • Using a poi that has not yet torn, try to scoop any goldfish of your choice that has not yet been scooped.

You act so as to maximize the expected value of the sum of the values of the scooped goldfish. This expected value can always be expressed as an irreducible fraction $\frac A B$. Let $B^{−1}$ be the inverse of $B$ modulo $\pmod {10^9 + 7}$. Find $A \times B^{-1} \pmod {10^9 + 7}$.

Input

$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$
  • All inputs are integers

Output

Output the answer on $1$ line.

Sample

Sample 1
Input
2 1 50
100 50
Output
500000066

It is optimal to first try to scoop goldfish $1$. In this case, the following $3$ courses of action are possible.

  1. You try to scoop goldfish $1$, and the poi tears (probability $\frac 1 2$).
  2. You scoop goldfish $1$. Next, you try to scoop goldfish $2$, and the poi tears (probability $\frac 1 4)$.
  3. You scoop goldfish $1$. Next, you scoop goldfish $2$ (probability $\frac 1 4$).

The expected value is $0 \frac 1 2 + 100 \frac 1 4 + 150 \frac 1 4 = \frac {125} 2$. Since the inverse of $2$ modulo $\pmod {10^9 + 7}$ is $5 \times 10^8 + 4$, output $125 \times (5 \times 10^8+4) \pmod {10^9+7} = 500000066$.

Sample 2
Input
1 100 99
100
Output
977688169
Sample 3
Input
4 1 0
3 1000 30 300
Output
1333

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。