No.766 Goldfish Scooping
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.
- You try to scoop goldfish $1$, and the poi tears (probability $\frac 1 2$).
- You scoop goldfish $1$. Next, you try to scoop goldfish $2$, and the poi tears (probability $\frac 1 4)$.
- 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もしくは右上の雲マークをクリックしてアカウントを作成してください。
ei1333333
treeone