PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
First, we consider the case where X, Y > 0. Let f(i) be the vector (S[i] S[i+1] 1), then there is a 3*3 matrix A such that f(i+1) = A f(i). Now, our task is calculating the number of vectors f(k) = (C m 1) satisfying L[i] <= k <= R[i], and 0 <= m < P.
The sequence f has a period r (at most P^2), since A is a regular matrix. That is f(k+r) = f(k), for all k >= 1.
The first part of solving the problem is calculating a period r and integers k which satisfy f(k) = (C m 1) for each m. Finding minimum k such that f(k+1) = f(1) is enough to calculate a period r. Therefore, we should search P+1 vectors in the sequence f, and it can be calculated by using baby-step-giant-step. At first, calculate the vectors A^d f(1) for 0 <= d < L, and store the vectors. For finding a vector v, we calculate (A^L)^e v for 0 <= e < r/L, and search these vectors in the set of all vectors A^d f(1). The precalculation takes O(L) time, and finding a vector in the sequence takes O(r/L) time if hashes are used for searching. Here, let’s set L = P^1.5, then this part takes O(P^1.5) + (P+1) * O(P^2 / P^1.5) = O(P^1.5) time.
The second part is calculating the answer for each intervals. It can be calculated by using binary search. It takes O(Q log P) time.
If X and/or Y are 0, above algorithm cannot be applied, because the matrix A may be singular. However, these cases are not so difficult. A similar method can be used for the case X > 0 or Y > 0, and the problem becomes trivial for the case X = Y = 0.
SETTER’S SOLUTION
Can be found here.