Author: Anton Trygub
Solved by:
First to solve: KNUTheNextLevelPlay
It is important to note that:
So, we just need to find the number of pairs , with 1\le i \le j \le n, for which (a_i + a_{i+1} + \ldots + a_{j})^2 - (a_i^2 + a_{i+1}^2 + \ldots + a_{j}^2) is divisible by . We will now describe a linear solution using prefix sums.
Let's denote:
Then, our task is to count the number of pairs , with 1\le i \le j \le n, for which (S_{j}-S_{i-1})^2 \equiv (T_{j}-T_{i-1}) \bmod 3 (here S_0=T_0=0). Now note that we only care about all these numbers modulo , so in fact we can group them into at most 3 \times 3 = 9 possible different values with 0 \leq x, y < 3.
This gives the following solution:
Let's keep an array , where dp[x][y] would be equal to the number of indices such that S_j \equiv x \bmod 3 and T_j \equiv y \bmod 3 which we have processed so far. Initially dp[0][0] = 1.
Process indices from left to right, and if you are processing index , add to answer dp[x][y] for every pair for which (S_i-x)^2 \equiv (T_i-y) \bmod 3, and update the corresponding entry in the table.