TooMuchExpectation | Topcoder Archive

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 R^Y * (R+P)^K-Y / (R+Q).

Find the expected value of weirdness: a fraction p/q. Return that fraction modulo 1,000,000,007.

Definition

Class:: TooMuchExpectation
Method:: findExpectedValue
Parameters:: int, long, int, int
Returns:: int
Method signature:: int findExpectedValue(int N, long P, int Q, int K)
(be sure your method is public)

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.

Examples

```
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.
```
100
```
```
100
```
```
100
```
```
100
```
```
Returns: 224580006
```

900000000

10000000000000000

Returns: 459797508

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.