ModCounters | Topcoder Archive

Problem Statement

You are given N "512-Modulo counters". Each 512-Modulo counter contains a value that is between 0 and 511, inclusive. Each counter allows an incrementation operation. Let's say the value of counter is x, then after the incrementation the value of counter will be (x + 1) % 512.

You are given an array S of length N with the initial value of each counter. Now, you are planning to perform K steps. In each step, you select a counter uniformly at random from the given N counters and increment it. You need to find the expected sum of the array after K steps. (Note that the sum is computed exactly, not modulo 512.)

Let your answer be R/Q, then you need to return (R*Q^-1) modulo (10⁹+7). See Notes for the explanation of Q^-1.

You are given integers A0, X, Y, N and an integer array P. Use the pseudocode below to generate the array S.

A[0] = A0
for i = 1 to N-1:
        A[i] = (A[i-1] * X + Y) modulo 1812447359

S = P
for i = size(P) to N-1:
        S[i] = A[i] modulo 512

Definition

Class:: ModCounters
Method:: findExpectedSum
Parameters:: int[], int, int, int, int, int
Returns:: int
Method signature:: int findExpectedSum(int[] P, int A0, int X, int Y, int N, int K)
(be sure your method is public)

Notes

It can be shown that the expected value of the sum of all counters is always a rational number R/Q such that Q and 1000000007 are relatively prime.
Q-1 denotes the inverse element to Q when computing modulo 1000000007. That is, (Q * Q-1) mod 1000000007 = 1.

Constraints

The length of P will be between 0 and min(N, 100) (inclusive)
Integers in P will be between 0 and 511 (inclusive)
A0 will be between 0 and 1812447358 (inclusive)
X will be between 0 and 1812447358 (inclusive)
Y will be between 0 and 1812447358 (inclusive)
N will be between 1 and 2000000 (inclusive)
K will be between 1 and 500000000 (inclusive)

Examples

```
{0, 511}
```
```
0
```
```
0
```
```
0
```
```
2
```
```
1
```
```
Returns: 256
```
After one step, the array has two equiprobable states : {0, 0} and {1, 511}. Hence, the expected sum = (0 + 512) / 2 = 256.
```
{0}
```
```
1001
```
```
1001
```
```
1001
```
```
2
```
```
2
```
```
Returns: 508
```
Here, the array is {0, 506}. Note that in the final array, the sum will be 508, independent of which counters are chosen in each step. Hence, the expected sum is 508.
```
{}
```
```
3583
```
```
1000
```
```
1812447358
```
```
2
```
```
2
```
```
Returns: 152
```
The array is {511, 23}. After 2 steps : the possible outcomes are {1, 23}, {0, 24}, {0, 24}, {511, 25}. Hence, the expected sum = 608 / 4 = 152.

{100, 101}

Returns: 856925612

{}

100000000

100000000

100000000

Returns: 454731206

{}

501296088

234548363

703491623

Returns: 804222535

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.