시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 76 | 61 | 54 | 84.375% |
For an array $[b_1, b_2, \dots , b_m]$ of integers, let’s define its weight as the sum of pairwise products of its elements, namely as the sum of $b_ib_j$ over $1 \le i < j \le m$.
You are given an array of $n$ integers $[a_1, a_2, \dots , a_n]$, and are asked to find the number of pairs of integers $(l, r)$ with $1 \le l \le r \le n$, for which the weight of the subarray $[a_l, a_{l+1}, \dots , a_r]$ is divisible by $3$.
The first line of the input contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the length of the array.
The second line contains $n$ integers $a_1, a_2, \dots , a_n$ ($0 \le a_i \le 10^9$) — the elements of the array.
Output a single integer — the number of pairs of integers $(l, r)$ with $1 \le l \le r \le n$, for which the weight of the corresponding subarray is divisible by $3$.
3 5 23 2021
4
5 0 0 1 3 3
15
10 0 1 2 3 4 5 6 7 8 9
20
In the first sample, the weights of exactly $4$ subarrays are divisible by $3$: