Số cách chia ba đoạn (Number of Ways)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng gồm $n$ số nguyên. Hãy đếm số cách chia toàn bộ mảng thành đúng ba đoạn liên tiếp, không rỗng, sao cho tổng của ba đoạn bằng nhau.

Một cách chia được xác định bởi hai vị trí cắt $i,j$ với

Ba đoạn tương ứng là

Input

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$.

Output

In số cách chọn hai vị trí cắt để ba đoạn nhận được có tổng bằng nhau.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n\le5\cdot10^5$

• $|a_i|\le10^9$

• Subtask 1 — 20%: $n\le40$

• Subtask 2 — 30%: $n\le5000$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

5
1 2 3 0 3

Output

2

Giải thích

Dãy là

có tổng bằng $9$, nên nếu chia được thì mỗi phần phải có tổng $3$.

Có hai cách:

• cắt sau vị trí $2$ và $3$: $[1,2]$, $[3]$, $[0,3]$;
• cắt sau vị trí $2$ và $4$: $[1,2]$, $[3,0]$, $[3]$.

Cả ba phần trong mỗi cách đều có tổng bằng $3$, nên đáp án là $2$.