ProductOfPrices
SRM 424 · 2008-11-05 · by Gluk
SRM 424 · 2008-11-05 · by Gluk · Geometry, Search, Simple Math
Problem Statement
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.
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.
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)
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.
1)
3 20 5 2 3 Returns: 64
2)
4 21 1 7 1 Returns: 3087
3)
10 100 4 37 11 Returns: 591860767
4)
13581 95224 350 92105 7812 Returns: 425853540
Submissions are judged against all 93 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ProductOfPrices with a public method int product(int N, int L, int X0, int A, int B) · 93 test cases · 2 s / 256 MB per case