P10740 [SEERC 2020] Divisible by 3

Define the weight of a sequence $b$ as $\sum_{i=1}^n \sum_{j=1}^{i-1} b_i \times b_j$. Now you are given an array $a$ of length $n$. Find how many pairs $(l, r)$ there are such that $1 \leq l \leq r \leq n$ and the weight of $[a_l, a_{l+1}, \ldots, a_r]$ is divisible by $3$.

The first line contains an integer $n\ (1 \leq n \leq 5 \times 10^5)$. Then follow $n$ integers $a_i\ (0 \leq a_i \leq 10^9)$.

Output the total number of valid pairs.

For the first sample, there are $4$ valid choices: $[1,1]$, $[2,2]$, $[3,3]$, and $[1,3]$. Translated by ChatGPT 5