ExpectedMinimumPower
SRM 730 · 2018-02-19 · by lg5293
Problem Statement
You are given two positive
You are going to choose x distinct integers, each between 1 and n, inclusive. The choice will be made uniformly at random. That is, each of the possible x-element subsets of the integers 1 to n is equally likely to be chosen.
Let S be the smallest integer among the x chosen ones. Let P be the expected value of 2^S. (In other words, P is the average value of 2 to the power of S, where the average is taken over all possible choices of the x distinct integers.)
It can be shown that P * (n choose x) is an integer. Compute and return this integer, modulo 10^9 + 7.
Notes
- In the statement, "(n choose x)" denotes the corresponding binomial coefficient - i.e., the number of ways to choose an x-element subset of a n-element set.
Constraints
- n will be between 1 and 10^9.
- x will be between 1 and min(n, 10^6).
4 4 Returns: 2
You have to choose all four numbers. Thus, S will be 1 and P will be 2^1 = 2.
3 2 Returns: 8
There are three equally likely scenarios: you will select either {1,2} or {1,3} or {2,3}. The corresponding values of S are 1, 1, and 2, respectively, and therefore P = 8/3. You should return the value P*(3 choose 2) = P*3 = 8.
3 1 Returns: 14
10 4 Returns: 1696
1000000000 1000000 Returns: 799728241
Submissions are judged against all 20 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ExpectedMinimumPower with a public method int findExp(int n, int x) · 20 test cases · 2 s / 256 MB per case