ProductAndProduct

SRM 763 · 2019-07-16 · by vivek1998299

SRM 763 · 2019-07-16 · by vivek1998299 · Advanced Math

Show categories

Class Name: ProductAndProduct

Return Type: int

Method Name: findExpectedProduct

Arg Types: (int, vector<int>, int, int)

Problem Statement

This problem has a non-standard time limit: 3 seconds.

There are N boxes in a row. The boxes are labeled 0 through N-1. Box i currently contains C[i] marbles.

Consider all possible ways of distributing M additional marbles into the boxes. We are going to choose one of these ways uniformly at random and we will distribute M additional marbles accordingly.

Formally, we are going to choose one sequence of nonnegative integers X[0], X[1], ..., X[N-1] such that sum(X) = M, and we will increment each C[i] by the corresponding X[i].

Once we distributed all the additional marbles, we will compute the product of the new numbers of marbles in all boxes. Let A/B be the expected value of that product as a reduced fraction, and let P be the prime number 998,244,353. Calculate and return the value (A*B^-1) modulo P, where B^-1 is the inverse of B modulo P.

You are given the int N, the int[] B, and the ints M and seed. Use the following pseudocode to generate the initial array C:

A[0] = seed
for i=1 to N-1:
    A[i] = (A[i-1]*1103515245 + 12345) modulo 2147483648

C = B
for i=size(B) to N-1:
    C[i] = A[i] modulo 998244353

Notes

Two ways of distributing the marbles (X0,X1,..XN-1) and (Y0,Y1,..YN-1) are considered different if Xi ≠ Yi for some i.

Constraints

N will be between 1 and 100,000, inclusive.
Number of elements in B will between 0 and min(N, 100), inclusive.
Each element of B will be between 0 and 998,244,352, inclusive.
M will be between 0 and 100,000, inclusive.
seed will be between 0 and 2,147,483,647, inclusive.

Examples

6
{}
9
1022219453
Returns: 349570005

5
{}
5
1888563433
Returns: 629258651

9
{}
10
796932720
Returns: 610929501

2
{}
7
295050285
Returns: 714395600

2
{}
8
162766991
Returns: 463554205

149)

3
{1, 2, 3}
0
0
Returns: 6

As M=0, we are not distributing any additional marbles. Formally, the only valid sequence is X = {0,0,0}, so we choose and apply this sequence. The final counts of marbles will be {1, 2, 3}, hence the expected value of their product is 1*2*3 = 6.

150)

3
{1, 2, 3}
1
0
Returns: 665496245

Now M=1, which means that we are adding one extra marble somewhere. After we do so, we will obtain one of the following three arrays C: {2, 2, 3}, {1, 3, 3}, or {1, 2, 4}. Each of these arrays will be generated with probability 1/3. Thus, the expected product is (2*2*3 + 1*3*3 + 1*2*4) / 3 = 29 / 3. We have 3-1 (mod P) = 332,748,118, and therefore the correct return value is (29 * 332,748,118) modulo P.

151)

4
{0,0,0,0}
3
0
Returns: 0

Regardless of how we distribute the three additional marbles, at least one C[i] will remain zero, and therefore the product will remain zero as well.

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

Coding Area

Language: C++17 · define a public class ProductAndProduct with a public method int findExpectedProduct(int N, vector<int> B, int M, int seed) · 153 test cases · 2 s / 256 MB per case