ProductAndProduct | Topcoder Archive

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

Definition

Class:: ProductAndProduct
Method:: findExpectedProduct
Parameters:: int, int[], int, int
Returns:: int
Method signature:: int findExpectedProduct(int N, int[] B, int M, int seed)
(be sure your method is public)

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

```
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.
```
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.
```
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.

{}

369273885

Returns: 164185046

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.