TooMuchExpectation
SRM 772 · 2019-12-10 · by vivek1998299
Problem Statement
You have a set S which contains N distinct objects numbered from 0 to N - 1. You are also given 3 integers P, Q, and K.
We are going to execute the following steps:
- Choose a subset A of S uniformly at random. (Each of the 2|S| possible subsets is chosen with the same probability.)
- Let R = |A|.
- Choose an integer Y uniformly at random from the set {0, 1, ..., K}.
- Compute the weirdness of your choices: the value RY * (R+P)K-Y / (R+Q).
Find the expected value of weirdness: a fraction p/q. Return that fraction modulo 1,000,000,007.
Notes
- Use 00 = 1.
- It is guaranteed that P modulo 1,000,000,007 is not equal to 0.
- If the correct answer is the reduced fraction p/q, the correct return value is (p*q-1) modulo 1,000,000,007, where q-1 is the inverse element to q.
- For inputs that meet the given constraints the correct return value always exists.
Constraints
- N will be between 1 and 900,000,000, inclusive.
- P will be between 1 and 10,000,000,000,000,000, inclusive.
- Q will be between 1 and 100,000, inclusive.
- K will be between 1 and 500, inclusive.
- P modulo 1,000,000,007 is not equal to 0.
721 400 828 329 Returns: 745150960
808 499 530 384 Returns: 100413881
831 325 865 54 Returns: 360470513
578 383 926 377 Returns: 608011535
598 636 963 255 Returns: 21662201
1 1 1 1 Returns: 625000005
The given set is S = {0}. We have four equally likely cases: We choose the subset {} and Y=0: weirdness is 00 * 11 / 1 = 1. We choose the subset {} and Y=1: weirdness is 01 * 10 / 1 = 0. We choose the subset {0} and Y=0: weirdness is 10 * 21 / 2 = 1. We choose the subset {0} and Y=1: weirdness is 11 * 20 / 2 = 1/2. Thus, the expected weirdness is (1 + 0 + 1 + 1/2) / 4 = 5/8. The correct return value is (5 * 8-1) modulo 1000000007 = (5 * 125000001) modulo 1000000007 = 625000005.
1 1 1 2 Returns: 750000006
Here the exact answer is 3/4.
Submissions are judged against all 154 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TooMuchExpectation with a public method int findExpectedValue(int N, long long P, int Q, int K) · 154 test cases · 2 s / 256 MB per case