TopCoder SRM 786 - 500: ModCounters

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 vector<int> , int , int , int , int , int
Returns int
Method signature int findExpectedSum(vector<int> P, int A0, int X, int Y, int N, int K)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 256

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)

Test cases

input
- P { 0, 511 }
- A0 0
- X 0
- Y 0
- N 2
- K 1
output
Returns 256

note

After one step, the array has two equiprobable states : {0, 0} and {1, 511}. Hence, the expected sum = (0 + 512) / 2 = 256.
input
- P { 0 }
- A0 1001
- X 1001
- Y 1001
- N 2
- K 2
output
Returns 508

note

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.
input
- P { }
- A0 3583
- X 1000
- Y 1812447358
- N 2
- K 2
output
Returns 152

note

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.
input
- P { 100, 101 }
- A0 5000
- X 50000
- Y 100000
- N 1000
- K 1000
output
Returns 856925612
input
- P { }
- A0 100000000
- X 100000000
- Y 100000000
- N 10
- K 1000
output
Returns 454731206
input
- P { }
- A0 501296088
- X 234548363
- Y 703491623
- N 2000000
- K 1894643
output
Returns 804222535