PROBLEM LINK:Author: Devendra Agarwal DIFFICULTY:HARD PREREQUISITES:Binary Indexed Trees/Segment Trees PROBLEM:Given fixed parameters R, p1, p2 (p1,p2 are primes) and array A, perform three operations: * 0 S D X Y: Add an AGP with the start term of S, the common difference of D, common ratio of R from the Xth to the to Yth element of A. * 1 X g: A[X] = (A[X])^{g} modulo p2. * 2 X Y: Output (A[X] + ...... + A[Y]) modulo p1. Array A can have upto 10^{5} elements and upto 10^{5} queries. EXPLANATION:We can see AGP as an infinite AGP. To add an AGP from [X,Y] is equivalent to adding 2 inﬁnite AGP’s which are: Now the solver can use any data structure such as BIT/segment tree. But since BIT are easy to implement and efficient, I will discuss the approach using BIT. Supose that using BIT, we somehow solve queries 0 and 2, how can we solve query 1 efficiently. Here we keep two BIT, one is modulo p1 (say BIT1) and other modulo p2 (say BIT2). For query 1 ie. 1 X g
Now, we have to answer queries 0 and 2. Let us analyse the situation after just one addition of query 0 (which is added at X, as we have broken 1 AGP into 2 infinite AGp’s). Let us find sum of all elements from 1 to J.
Multiplying with R, we get Subtracting above 2 equations, we get Simplifying, we get
Let Let Let Note:(a) BADD, T and Z are independent of query point J. By using Fact (a), we can store BADD, T and Z in the BIT (as it is independent of query point) in the update query 0 and use fact (b) for query of type 2. Solution is not yet complete as we need to augment our data structure with yet another field ADD, which keeps the constant addition of the value in the index. This is used intially and for query 1. So, the output of query 2 changes from (b) to: (c) Wait, the solution is not yet over! What if (R1)^{2} is not coprime to prime numbers, then we won't be able to find INVERSE of it and hence our solution will fail. In this case, the problem transforms to AP as R mod prime = 1 mod prime. Solve for AP in the similar idea using data structures. Complexity of solution is O( N * log(N) ) intially, plus O ( log(N) ) for each query. So overall complexity is O( (N+Q)* log(N)). See setter's solution for implementation details using the above idea. ALTERNATE SOLUTION:(as told by @triveni) But actually we can do something better here. sum(i) = S + (S+D)*R + (S+2D)*R^2 + (S+3D)*R^3 +....+ (S+(i1)*D)*R^(i1) Now, what one can do is pretty simple. Just precompute the value of X(i) and Y(i) for all 1<=i<=N.
This method doesn't assume anything about primeness of p1 and p2. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 12 May '14, 15:14
showing 5 of 7
show all

There was no need of computing any kind of inverse modulo or such things at all to solve this problem, using the method that I followed. Even if p1 and p2 are not primes, this problem can be solved very easily using the same approach. I used Segment Tree data Structure. In my opinion, the hardest part to solve this problem is to find the sum of the AGP in efficiently. It is said in the editorial, we need to compute Modulo((R1)**2). But actually we can do something better here. sum(i) = S + (S+D)R + (S+2D)R^2 + (S+3D)R^3 +....+ (S+(i1)D)R^(i1) Now, what one can do is pretty simple. Just precompute the value of X(i) and Y(i) for all 1<=i<=N.
This method doesn't assume anything about primeness of p1 and p2. answered 13 May '14, 02:27
very good solution that you have provided i also stucked in the same part but the way you solved it is amazing ..
(13 May '14, 10:51)
great solution
(13 May '14, 14:39)
2
I have also added this solution to editorial, thanks for the approach!
(13 May '14, 15:46)

May i know, for which testcase, it failed http://www.codechef.com/viewsolution/3872050 answered 12 May '14, 19:36
Hi miiitd6979672,
(13 May '14, 20:07)

@all As we all know there are many ways to solve this problem .we can use any of the two available data structures BIT/segment tree. BIT solution is described by @darkshadows and an easy approach is descibed by triveni to handle complex part in this question but i dont know why i am only able to get AC using triveni's approach and if i am using modulo inverse approach i am continuously getting WA. can any one check this solution and tell me where is the problem http://www.codechef.com/viewsolution/3902074 +1 to the problem setter +1 to the darkshadows for providing approach using BIT +1 to the triveni answered 13 May '14, 13:34
Hi kodos,
1 Answer should be 0 and you are getting 4
(13 May '14, 17:03)
@all @darkshadows Please explain the complexity of query type 0 . By my understanding, if query of type 0 starts from 1 and end at N then updating the bit will be of O(N * logN ) [No of elements to update * complexity of one update], so if there are M queries of type 0 then compelity can be M * N * logN which will exceed the time limit.
(27 May '14, 13:28)

^I'm in exactly the same situation. Maybe it has to do with this part "What if (R1)2 is not coprime to prime numbers". Though my solution http://www.codechef.com/viewsolution/3900035 (solved using sqrtdecomposition) gives a WA regardless. Surprisingly no AC solution uses square root decomposition.
Also some cheating cases: http://www.codechef.com/viewsolution/3875556 http://www.codechef.com/viewsolution/3878413
Report cheating cases to admin via mail.
Can you explain in detail how to solve when (R1)^2 is not comprime to prime nos? How does the problem transform to an AP?
(R1)^2 not coprime to a prime p means that gcd(p,(R1)^2) > 1. However, since p is prime, that means gcd can only be p, so p(R1)^2. This is equivalent to saying R = 1 mod p, which means that S+(S+D)R + (S+2D)R^2 + ... + (S+nD)R^n = S+(S+D)+(S+2D)+...+(S+nD) mod p
got it, thanks!
@all @darkshadows Please explain the complexity of query type 0 . By my understanding, if query of type 0 starts from 1 and end at N then updating the bit will be of O(N * logN ) [No of elements to update * complexity of one update], so if there are M queries of type 0 then compelity can be M * N * logN which will exceed the time limit.
@devuy11 can you please explain this ?