RiggedLottery | Topcoder Archive

Problem Statement

In a traditional lottery, the players are trying to guess a set of K numbers that is selected at random. The K numbers are distinct and each of them is between 0 and N-1, inclusive. Usually, the chances of winning in such a lottery are very small. However, it has come to your attention that your local lottery may be biased. You now want to analyze this bias.

Your source has sent you pseudocode of the algorithm used by your local lottery. The pseudocode is shown below. The values returned by the function random() are mutually independent.

def random(P):
    generate and return a random value between 0 and N-1, inclusive,
    in such a way that the probability of returning value i is P[i] / 1000

def lottery(K,P):
    selected_numbers = an empty set
    while selected_numbers has fewer than K elements:
        candidate = random(P)
        if candidate is not in selected_numbers:
             add candidate to selected_numbers
    return selected_numbers

You are given the int K and the int[] P: the probability distribution used in the pseudocode. Your favorite number is the number 0. You would like to compute the probability that this number will be among the K selected numbers. This probability can be expressed as an irreducible fraction Q / R. It can be shown that under the constraints of this problem there exists exactly one integer Y between 0 and 10^9+6, inclusive, that satisfies the modular equation R * Y = Q (mod 10^9+7). Return the value of Y.

Definition

Class:: RiggedLottery
Method:: getProbability
Parameters:: int, int[]
Returns:: int
Method signature:: int getProbability(int K, int[] P)
(be sure your method is public)

Constraints

N will be between 1 and 50, inclusive.
K will be between 1 and N, inclusive.
P will contain exactly N elements.
Each element in P will be between 1 and 1000, inclusive.
The sum of all elements of P will be 1000.

Examples

```
1
```
```
{300,250,450}
```
```
Returns: 100000001
```
In this lottery we are selecting one number from the set {0,1,2}. The number 0 is selected with the probability 300/1000. The corresponding irreducible fraction is 3/10. The correct return value is 100000001 because 10 * 100000001 = 3 (mod 10^9+7).
```
2
```
```
{200,600,200}
```
```
Returns: 350000003
```
The probability that 0 is the first number added to selected_numbers is obviously 0.2. It can be computed that the probability that 0 is the second number added to selected_numbers is 0.35. As these two options are mutually exclusive, the total probability that 0 is selected is 0.55 = 11/20. We have 20 * 350000003 = 11 (mod 10^9+7).
```
3
```
```
{100, 500, 400}
```
```
Returns: 1
```
```
4
```
```
{30,799,92,66,13}
```
```
Returns: 233159814
```

{13,8,49,2,12,69,30,22,21,48,18,8,37,30,13,10,12,30,15,63,33,38,46,10,93,52,26,11,13,14,19,48,1,9,5,31,7,4,10,20}

Returns: 959464924

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.