Background

Luogu’s testdata is only for community communication and is not official testdata. Official judging link: https://www.cspro.org/.

Problem Description

Xiaolin is playing a gacha game. There are $n$ different types of cards, numbered from $1$ to $n$. Each draw gives her a type $i$ card with probability $p_i$. If she has already obtained this card before, it will be converted into a coin. She can use $k$ coins to exchange for one card that she has not obtained yet.

Xiaolin will keep drawing until she has collected all types of cards. Find the expected number of draws. If the absolute error between your answer and the standard answer is at most $10^{-4}$, it will be considered correct.

Hint: Smart Xiaolin will keep the coins, and when exchanging can obtain all remaining cards, she will exchange them all at once and stop drawing.

Input Format

Read from standard input.

There are two lines. The first line contains two positive integers $n, k$ separated by spaces. The second line gives $p_1, p_2, \dots, p_n$, separated by spaces.

Output Format

Write to standard output.

Output one line with a real number, the expected number of draws.

2 2
0.4 0.6

2.52

4 3
0.006 0.1 0.2 0.694

7.3229920752

Hint

Sample 1 Explanation

There are $2$ types of cards. Let them be A and B, with probabilities $0.4$ and $0.6$. $2$ coins can be exchanged for one card. The possible cases are:

• The first draw gets A, the second draw gets B, then it ends. Probability $0.4 \times 0.6 = 0.24$, number of draws $2$.
• The first draw gets A, the second draw gets A, the third draw gets B, then it ends. Probability $0.4 \times 0.4 \times 0.6 = 0.096$, number of draws $3$.
• The first draw gets A, the second draw gets A, the third draw gets A, exchange coins for B, then it ends. Probability $0.4 \times 0.4 \times 0.4 = 0.064$, number of draws $3$.
• The first draw gets B, the second draw gets A, then it ends. Probability $0.6 \times 0.4 = 0.24$, number of draws $2$.
• The first draw gets B, the second draw gets B, the third draw gets A, then it ends. Probability $0.6 \times 0.6 \times 0.4 = 0.144$, number of draws $3$.
• The first draw gets B, the second draw gets B, the third draw gets B, exchange coins for A, then it ends. Probability $0.6 \times 0.6 \times 0.6 = 0.216$, number of draws $3$.

So the answer is $0.24 \times 2 + 0.096 \times 3 + 0.064 \times 3 + 0.24 \times 2 + 0.144 \times 3 + 0.216 \times 3 = 2.52$.

Subtasks

For $20\%$ of the data, $1 \leq n, k \leq 5$.

For another $20\%$ of the data, all $p_i$ are equal.

For $100\%$ of the data, $1 \leq n \leq 16$, $1 \leq k \leq 5$, all $p_i$ satisfy $p_i \geq \frac{1}{10000}$, and $\sum_{i=1}^{n} p_i = 1$.

Constraints

Translated by ChatGPT 5