CandyDrawing | Topcoder Archive

Problem Statement

There are N boxes, numbered 1 through N. For each i, box i contains exactly i candies and one pebble. Thus, there are exactly i+1 objects in box i.

We are now going to create a collection of N objects using the following simple procedure: from each box, we will draw one object uniformly at random.

Let p be the probability that our collection will contain exactly K candies. You are given the ints N, K, and MOD. Return the value (p * (N+1)!) modulo MOD.

Definition

Class:: CandyDrawing
Method:: findProbability
Parameters:: int, int, int
Returns:: int
Method signature:: int findProbability(int N, int K, int MOD)
(be sure your method is public)

Constraints

N will be bewteen 1 and 1,000,000,000 (inclusive).
K will be between 0 and 2,000 (inclusive).
MOD will be between 1,000,000,000 and 2,000,000,000 (inclusive).
MOD will be a prime.

Examples

```
2
```
```
1
```
```
1000000007
```
```
Returns: 3
```
We have two boxes: box 1 with a candy and a pebble, and box 2 with two candies and a pebble. We are looking for the probability of drawing exactly one candy. This can happen in two different ways: either we draw the candy from box 1 and the pebble from box 2, or vice versa. The probability of the first way is (1/2)*(1/3) = 1/6. The probability of the second way is (1/2)*(2/3) = 1/3. Thus, the total probability is p = 1/6 + 1/3 = 1/2. We have p * (N+1)! = p*6 = 3, therefore the answer is (3 mod 1,000,000,007) = 3.
```
3
```
```
2
```
```
1000000007
```
```
Returns: 11
```
```
10
```
```
4
```
```
1000000007
```
```
Returns: 157773
```

1000000000

1000000009

Returns: 629516825

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.