Number of ways

In how many ways can an array of $n$ integers be cut into three non-empty blocks of consecutive elements with equal sums? In other words, count the pairs $(i, j)$, $2 \le i \le j \le n - 1$, such that $\sum_{k=1}^{i-1} a_k = \sum_{k=i}^{j} a_k = \sum_{k=j+1}^{n} a_k$.

The first line contains $n$ ($1 \le n \le 2 \cdot 10^5$). The second line contains $n$ integers ($|a_i| \le 10^9$).

A single number — the number of ways.

If the total $S$ is not divisible by $3$, the answer is $0$. Otherwise the first cut is where $p_{i-1} = S/3$ and the second where $p_j = 2S/3$. Move $j$ from left to right and add the number of earlier prefixes with $p = S/3$ — $O(n)$.

For $S = 0$ both conditions coincide — the cuts must not fall at the same place. If all numbers are zero, the answer is $\binom{n-1}{2}$, up to $2 \cdot 10^{10}$ — a 64-bit type is needed.

Source: Codeforces, problem 466C.