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 |
| 0) | |
| | | 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. |
|
|
| 1) | |
| | |
| 2) | |
| | |
| 3) | |
| | |
| 4) | |
| | 5 | 200000 | 999999999 | 123456789 | 987654321 |
| Returns: 499739175 | |
|