CountSubarrays | Topcoder Archive

Problem Statement

You are given an array A containing N elements. You are also given an integer X. Count the number of ordered pairs (L, R), such that:

0 ≤ L ≤ R < N.
(A[L] * A[L+1] * ... * A[R]) modulo 744,444,499 = X.

The array A is given in the following format: You are given the int[] Aprefix and the ints n, a, b, and m. Use the following pseudocode to generate A:

for i = 0 to length(Aprefix)-1:
    A[i] = Aprefix[i]
for i = length(Aprefix) to n-1:
    A[i] = ( A[i-length(Aprefix)] * a + b ) modulo m

Definition

Class:: CountSubarrays
Method:: count
Parameters:: int[], int, int, int, int, int
Returns:: long
Method signature:: long count(int[] Aprefix, int n, int a, int b, int m, int X)
(be sure your method is public)

Constraints

n will be between 1 and 94,749, inclusive.
Aprefix will contain between 1 and n elements, inclusive.
Aprefix will contain at most 200 elements.
Each element of Aprefix will be between 0 and 744,444,498, inclusive.
m will be between 1 and 744,444,499, inclusive.
Each of a and b will be between 0 and m-1, inclusive.
X will be between 0 and 744,444,498, inclusive.

Examples

```
{2,1,2}
```
```
3
```
```
5
```
```
7
```
```
11
```
```
2
```
```
Returns: 4
```
We are looking for all subarrays of {2,1,2} that have product (modulo 744,444,499) equal to 2. There are four such subarrays. The corresponding pairs (L,R) are (0,0), (0,1), (1,2), and (2,2).
```
{1}
```
```
3
```
```
0
```
```
0
```
```
744444499
```
```
0
```
```
Returns: 5
```
The array you should generate is {1,0,0}, and we are counting subarrays whose product is 0. There are five such subarrays: all of them, except for (0,0).

{332561219,121884851,427632830,369957091,549417829,685227621,436551677,351304445,243813223,371998688}

330563283

311776610

744444499

222370756

Returns: 8

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.