CandyDrawing
SRM 629 · 2014-07-26 · by dreamoon
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
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.
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 1000 1000000009 Returns: 629516825
892314287 1808 1999993927 Returns: 1374427440
Submissions are judged against all 34 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CandyDrawing with a public method int findProbability(int N, int K, int MOD) · 34 test cases · 2 s / 256 MB per case