TooNewbie's blog

By TooNewbie, 8 years ago, In English

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:

cb5d37e9285f97f27e437b7e92b319a2

For example, the sympathetic table A, 3 by 4 for a given x looks like:

b21e31a220a43ecc0233c3f9640fc13e

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 :)

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.