StrawberryHard | Topcoder Archive

Problem Statement

This problem has an unusual time limit of 5 seconds.

Teja and Raja are experienced players in CSGo (Catch the Strawberry and go). CSGo is a two-player game consisting of n rounds. Teja and Raja play alternate rounds, Teja goes first. (Thus, Teja plays rounds 1, 3, 5, ..., while Raja plays rounds 2, 4, 6, ...)

At the beginning of the entire game Teja and Raja each have zero strawberries. In each round of CSGo, the active player can gain between 0 and 2*k strawberries. The actual number of strawberries gained is a random event (more details below) and all these random events are mutually independent.

You are given the values n, k, Arange, Brange, and seed. Use the following pseudocode to generate arrays A and B, each of length 2*k+1:

state = seed
for i = 0 .. 2*k:
    state = (1103515245 * state + 12345)
    state = state modulo 2^31
    A[i] = state modulo Arange
    state = (1103515245 * state + 12345)
    state = state modulo 2^31
    B[i] = state modulo Brange

For each valid index i, let pA(i) = A[i] / sum(A) and let pB(i) = B[i] / sum(B). The value pA(i) is the probability that Teja gains exactly i strawberries in any one round in which he is the active player. The value pB(i) is the same for Raja.

For spectators a game of CSGo is competitive if the absolute difference between the number of Teja's and the number of Raja's strawberries never exceeds k. (I.e., after each round the difference must be k or less.)

What is the probability with which the game between Teja and Raja will be competitive? It can be shown that the answer is always rational. Let X/Y be the answer in reduced form. Let Z = Y^(-1) be the inverse element to Y when computing modulo 10^9 + 7. Compute and return the value (X*Z) modulo 10^9 + 7.

Definition

Class:: StrawberryHard
Method:: competitive
Parameters:: int, int, int, int, int
Returns:: int
Method signature:: int competitive(int n, int k, int Arange, int Brange, int seed)
(be sure your method is public)

Notes

The inverse element to Y when computing modulo 10^9 + 7 is the only Z in the range [0, 10^9 + 6] such that Y*Z = 1 (modulo 10^9 + 7).
The constraints ensure that the answer is always well-defined: the probability is always a fraction X/Y such that Y has a unique inverse element.

Constraints

n will be between 1 and 17 inclusive.
k will be between 1 and 7000 inclusive.
Arange and Brange will be between 1 and 10^9+7 inclusive.
seed will be between 0 and 10^9+6 inclusive.
Sum of elements of A will not be a multiple of 10^9+7.
Sum of elements of B will not be a multiple of 10^9+7.

Examples

```
1
```
```
3
```
```
2
```
```
7
```
```
0
```
```
Returns: 571428576
```
The pseudocode should give you the arrays A = {1,1,1,1,1,1,1} and B = {2,3,0,0,1,1,0}. This game consists of just one round in which Teja gains some strawberries. If Teja gains between 0 and 3 strawberries, the game will be competitive, if he gains more, it won't be. The probability that Teja gains between 0 and 3 strawberries is 4/7. Thus, we have X = 4 and Y = 7. We can compute that Z = 142,857,144 and therefore the answer you should return is (X*Z) modulo (10^9 + 7) = 571,428,576.
```
6
```
```
3
```
```
3
```
```
3
```
```
740562
```
```
Returns: 1
```
The arrays are A = {1, 2, 0, 0, 0, 0, 0} and B = {1, 1, 0, 0, 0, 0, 0}. This game has six rounds. In each round, the active player gains at most one strawberry. (Note that the probability of gaining more strawberries is zero.) Thus, the difference between the numbers of Teja's and Raja's strawberries never exceeds 3 and the game is guaranteed to be competitive.
```
7
```
```
3
```
```
3
```
```
3
```
```
740562
```
```
Returns: 753086426
```
If Teja always gains a strawberry and Raja never does, the game will not be competitive. Thus, the probability that this game won't be competitive is (2/3)^4 * (1/2)^3.
```
7
```
```
5
```
```
11
```
```
13
```
```
47
```
```
Returns: 931930680
```

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.