Problem link : contest practice
Difficulty : EasyMedium
Prerequisites : Geometry, Number Theory
Problem :
There is a rectangle R on the Cartesian plane. The corner points of R are (0, 0), (0, H), (W, H) and (W, 0).
A simple polygonal chain P is placed in the rectangle. P can be described as following:
 P consists of N points, both coordinates of which are integers;
 The points are indexed with integers from 0 to N  1;
 Xcoordinate of i'th point of P equals to X_{i};

Ycoordinate of i'th point of P equals to:
 0, if i is even;
 H, if i is odd.
 X_{0} equals to 0;
 X_{i} < X_{i + 1} for 0 ā¤ i < N  1
 X_{N  1} equals to W.
Your task is pretty simple: calculate the area of R, which is lying under P.
N can be extremely huge in this problem, so itās impossible to give you array X itself. Instead of this, we will provide some additional variables and arrays, with a help of which you will be able to generate array X inside your program.
We will use additional integer variables M, A, B and IND. Also, additional array D, which consists of M integers and is indexed with integers from 0 to M  1 will be used.
 1 ā¤ M;
 0 ā¤ A, B, IND < M;
 1 ā¤ D_{i} < 10^{4}.
Hereās a pseudocode, which generates array X:
X[0] = 0
for i from 1 to N  1:
begin
X[i] = X[i  1] + D[IND]
IND = (A * IND + B) % M
end
</pre>
Explanation
Now the area under the polygonal line can be found by finding the sum of areas of triangles formed by (X_{i},0), (X_{i+2},0) and (X_{i+1},H), where i=2*k (k>=0).
Our answer = (1/2)*H*(X_{2}X_{0} + X_{4}X_{2} + X_{6}X_{4} ā¦ X_{N1}X_{N3})
=(1/2)*H*(X_{N1}X_{0})
=(1/2)*H*W
So, we need to just find W which is equal to X_{N1}. We are already given H in the question.
How to get 34 points
N is upto 524288 and M is upto 524288. We can easily generate the array X in O(N). X_{N1} is W.
How to get (100) points
If we look at pseudo code for generating array X, we can see that IND can have atmost M distinct values. For each value of IND, there will always be a fixed value of next IND because it depends on constants A,B and M. So there will be always a cycle of length atmost M in the values of IND.
So, we first find the length of the cycle(we stop when we reach a value which has already been reached before). Finding cycle will be O(length of cycle). Letā say the cycle is A_{1},A_{1}ā¦A_{K}, where A_{i} denotes the values of IND visited. Letās say SUM=sum[i=1 to K]{D[A_{i}]}.
Now, we know that this cycle is completed N/K times(our answer will be SUM*(N/K) after these many cycles) and also first N%K elements of this cycle are included. So, in our answer we also add sum[i=1 to N%K]{D[A_{i}]}.
Complexity is O(M) worst case.
Note: Using double to store the answer will not pass WALL because of precision problem. Use ālong doubleā instead, or just use ālong longā and print ā.5ā or ā.0ā manually.