ProductOfPrices | Topcoder Archive

Problem Statement

There are N trees numbered 0 to N-1, and you must plant them along a straight line. Tree i will be planted at coordinate X[i], where X is constructed using the following recursive definition:
X[0] = X0 MOD L
X[i] = (X[i-1]*A+B) MOD L (note that X[i-1]*A+B may overflow a 32-bit integer)
The price of planting tree i is the sum of the distances between tree i and each tree numbered less than i. Calculate the product of the prices of all the trees (except tree 0), and return this number modulo 1,000,000,007.

Definition

Class:: ProductOfPrices
Method:: product
Parameters:: int, int, int, int, int
Returns:: int
Method signature:: int product(int N, int L, int X0, int A, int B)
(be sure your method is public)

Constraints

N will be between 2 and 200,000, inclusive.
L will be between 1 and 200,000, inclusive.
X0,A,B will each be between 0 and 1,000,000,000, inclusive.

Examples

```
5
```
```
10
```
```
3
```
```
1
```
```
1
```
```
Returns: 180
```
The trees are planted at positions: 3, 4, 5, 6, 7. Their prices are (starting from tree 1): 1, 3, 6, 10. The product of prices is 1 * 3 * 6 * 10 = 180.
```
3
```
```
20
```
```
5
```
```
2
```
```
3
```
```
Returns: 64
```
```
4
```
```
21
```
```
1
```
```
7
```
```
1
```
```
Returns: 3087
```
```
10
```
```
100
```
```
4
```
```
37
```
```
11
```
```
Returns: 591860767
```

999999999

123456789

987654321

Returns: 499739175

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.