Divisible by 3#12839

Divisible by 3 (Editorial)

Author: Anton Trygub

Solved by:

First to solve: KNUTheNextLevelPlay

It is important to note that:

\sum_{1\le i < j \le m} b_ib_j = \frac{(b_1 + b_2 + \ldots + b_m)^2 - (b_1^2 + b_2^2 + \ldots + b_m^2)}{2}

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:

S_i = a_1 + \ldots + a_i
T_i = a_1^2 + \ldots + a_i^2

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.