ProductQuery | Topcoder Archive

Problem Statement

Mrs. Jeipouju took part in a programming contest. One of the problems was as follows:

You are given an array A containing N integers. Each element of A is an integer between 0 and 9, inclusive. You are also given two arrays Qfrom and Qto, containing Q elements each. For each i, Qfrom[i] and Qto[i] describe the i-th query: you must take all elements of A with indices between Qfrom[i] and Qto[i], inclusive, and calculate their product modulo 10. Output exactly Q integers. The i-th number of the output must be the answer to the i-th query.

Mrs. Jeipouju made an input for this task by herself and generated the output using her program. However, she erased the array A by mistake - now she only knows int N, int[] Qfrom, int[] Qto and int[] output (output[i] is the i-th integer generated by her program). Return the number of possible arrays A, modulo 1,000,000,007. If there are no possible arrays A (i.e. her program is definitely wrong), return 0.

Definition

Class:: ProductQuery
Method:: theInput
Parameters:: int, int[], int[], int[]
Returns:: int
Method signature:: int theInput(int N, int[] Qfrom, int[] Qto, int[] output)
(be sure your method is public)

Constraints

N will be between 1 and 100, inclusive.
Qfrom, Qto and output will contain the same number of elements.
Qfrom, Qto and output will contain between 1 and 50 elements, inclusive.
Each element of Qfrom and Qto will be between 0 and N-1, inclusive.
For each i, Qto[i] will be greater than or equal to Qfrom[i].
Each element of output will be between 0 and 9, inclusive.

Examples

```
3
```
```
{0}
```
```
{0}
```
```
{5}
```
```
Returns: 100
```
A[0] must be 5. A[1] and A[2] are arbitrary integers between 0 and 9.
```
5
```
```
{0, 2, 0}
```
```
{1, 4, 4}
```
```
{3, 4, 6}
```
```
Returns: 0
```
Mrs. Jeipouju's program is definitely wrong.
```
3
```
```
{0, 1}
```
```
{1, 2}
```
```
{5, 8}
```
```
Returns: 4
```
There are 4 possible inputs: A[0] = 5, A[1] = 1, A[2] = 8 A[0] = 5, A[1] = 3, A[2] = 6 A[0] = 5, A[1] = 7, A[2] = 4 A[0] = 5, A[1] = 9, A[2] = 2

{2, 0, 3, 6}

{3, 7, 4, 6}

{2, 0, 6, 7}

Returns: 118080

{9, 6, 2, 3, 1, 3, 12, 3, 4, 6, 10, 18, 10, 11, 15, 5}

{12, 12, 4, 13, 7, 14, 17, 10, 5, 13, 11, 19, 17, 14, 17, 8}

{7, 5, 7, 5, 0, 5, 8, 5, 3, 5, 3, 9, 4, 1, 6, 5}

Returns: 276398080

```
58
```
```
{5, 5}
```
```
{8, 8}
```
```
{1, 2}
```
```
Returns: 0
```

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.