Hello Codeforces, I need your help.
Given rectangular table A with n rows and m columns. This table has n × m cells, numbered sequentially with positive integers from top to bottom, from left to right. A[i][j] is a cell of rectangular table A at the cross of i-th row and j-th column. For the given value of x the sympathetic table is a table A with values in the cells equal to x in power of number of the corresponding cell. More formally A[i][j] = x(i−1)∗m + j.
Given q queries of rectangular borders x1, x2, y1, y2 and modulo p, the answer for such query is the sum of numbers in corresponding rectangle by modulo.
More formally, find:
For example, the sympathetic table A, 3 by 4 for a given x looks like:
Constraints:
1 ≤ n, m, x, p ≤ 109
1 ≤ q ≤ 104
1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m.
I spent much time for that problem, but I couldn't solve, please help me. Thanks in advance :)
Just take sum of first row by using Geometric Progression Sum Formula. Let's call this sum S. Sum of second row will be S * x^m. Sum of third row will be S * x^m * x^m. Another geometric progression.