JOIN
Get Time

   Problem Statement  

 Problem Statement for LimitedMemorySeries2

Problem Statement

    Due to some infrastructure limits the memory limit is set to 13 MB. Note that this should correspond to an actual memory limit of only 1 MB. If your solution allocates more than 1 MB of memory, it may exceed the memory limit.

You are given an array X[0..n-1] of integers. For each i between 0 and n-1, inclusive, the radius of element i is the largest k with the following properties:

  • Both i-k and i+k are valid indices into the array. That is, i-k >= 0 and i+k < n.
  • The value X[i] is the strict maximum among the values X[i-k], X[i-k+1], ..., X[i+k]. (Here, "strict" means that the values at all other indices must be strictly smaller.)

For example, in the array X = {4,4,4,4,4} the radius of each element is 0, and in the array X = {10,20,30,20} the radius of element 2 (0-based index) is 1.

Your task is to find the radius of each element of X and to compute the sum of all those radii. Right now, this seems like a fairly standard problem. Here's the catch: the memory limit in this problem is really small. So small that you cannot even store the array X into memory.

You are given the int n and the longs x0, a, and b. Use the following pseudocode to generate the array X:

X[0] = x0
for i = 1 to n-1:
        X[i] = ((X[i-1] XOR a) + b) AND ((2^50) - 1)

In the above pseudocode, XOR and AND are the standard operators "bitwise xor" and "bitwise and".

Return the sum of radii of all elements of X, modulo 1,000,000,007.

 

Definition

    
Class:LimitedMemorySeries2
Method:getSum
Parameters:int, long, long, long
Returns:int
Method signature:int getSum(int n, long x0, long a, long b)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 10,000,000, inclusive.
-x0, a and b will be between 0 and 2^50-1, inclusive.
 

Examples

0)
    
6
2
23
1
Returns: 2
In this case, the generated array is X = {2,22,2,22,2,22}. The radii of its elements are {0,1,0,1,0,0}. The correct return value is 0+1+0+1+0+0 = 2.
1)
    
100
0
0
1
Returns: 0
Here, the generated array is {0,1,...,99}. The radius of each element is zero, so the answer is zero in this case.
2)
    
234234
1125899906842623
123456789123456
987654321549687
Returns: 1144970
Don't forget, the answer is modulo 1,000,000,007.
3)
    
10000000
12345678912345
98765094309812
34893049812392
Returns: 65420804
It is highly recommended to test this example in the arena before submitting.

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 681 Round 1 - Division I, Level Two