Uchga teng bo'lish

$n$ ta butun sondan iborat massivni uchta bo'sh bo'lmagan ketma-ket qismga yig'indilari teng bo'ladigan qilib necha xil usulda bo'lish mumkin? Boshqacha aytganda, $2 \le i \le j \le n - 1$ bo'lgan va $\sum_{k=1}^{i-1} a_k = \sum_{k=i}^{j} a_k = \sum_{k=j+1}^{n} a_k$ shartini qanoatlantiradigan $(i, j)$ juftliklar sonini toping.

Birinchi qatorda $n$ ($1 \le n \le 2 \cdot 10^5$). Ikkinchi qatorda $n$ ta butun son ($|a_i| \le 10^9$).

Bitta son — usullar soni.

Umumiy yig'indi $S$ $3$ ga bo'linmasa, javob $0$. Aks holda birinchi kesish $p_{i-1} = S/3$ bo'lgan joyda, ikkinchisi $p_j = 2S/3$ bo'lgan joyda. $j$ ni chapdan o'ngga yuritib, undan oldingi $p = S/3$ bo'lgan prefikslar sonini qo'shib boring — $O(n)$.

$S = 0$ bo'lsa, ikkala shart bir xil — kesishlar bir joyga tushmasligi kerak. Hamma son nol bo'lsa, javob $\binom{n-1}{2}$, ya'ni $2 \cdot 10^{10}$ gacha — 64 bitli tur kerak.

Manba: Codeforces, 466C-masala.