Connection Status:
Competition Arena > ModCounters

ModCounters

SRM 786 · 2020-05-14 · by jeel_vaishnav

SRM 786 · 2020-05-14 · by jeel_vaishnav · Math
Class Name: ModCounters
Return Type: int
Method Name: findExpectedSum
Arg Types: (vector<int>, int, int, int, int, int)
Problem Statement

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 (109+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

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)
{478, 135, 287, 286, 238}
361711600
88187871
415501685
5
1398216
Returns: 907283075
1)
{}
340768325
829723516
96319779
5
981603
Returns: 935400859
2)
{388, 302, 153, 212, 38}
585703634
230851803
445950441
5
5
Returns: 1098
3)
{147, 83, 374, 337, 500}
528048293
842093637
941135252
5
10
Returns: 1451
4)
{}
510069165
284814936
867995759
5
20
Returns: 1621
99)
{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.

100)
{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.

101)
{}
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.

Submissions are judged against all 121 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ModCounters with a public method int findExpectedSum(vector<int> P, int A0, int X, int Y, int N, int K) · 121 test cases · 2 s / 256 MB per case

Submitting as anonymous