Tutorial — Phân Chia Đoạn Số

Tổng của cả dãy số phải chia hết cho $3$, vì cả ba phần liên tiếp cần có tổng bằng nhau. Nếu tổng toàn mảng không chia hết cho $3$, số cách chia thỏa mãn chắc chắn bằng $0$.

Gọi $T$ là tổng của một phần, điều kiện để vị trí cắt đầu tiên tại chỉ số $p$ và vị trí cắt thứ hai tại chỉ số $j$ hợp lệ là $P[p] = T$ và $P[j] = 2T$ với $1 \le p < j \le n - 1$, trong đó $P[x]$ là tổng tiền tố đến chỉ số $x$.

Việc duyệt qua tất cả các cặp chỉ số $(p, j)$ sẽ tốn độ phức tạp thời gian $O(n^2)$, không thể vượt qua giới hạn thời gian. Chúng ta có thể tối ưu bằng cách chỉ duyệt chỉ số $j$ và duy trì số lượng chỉ số $p < j$ có $P[p] = T$.

Duyệt một lượt từ trái sang phải, dùng biến đếm $C$ để tích lũy số vị trí có $P[p] = T$, và khi gặp $P[j] = 2T$ với $j \ge 2$, cộng $C$ vào đáp số để đạt độ phức tạp $O(n)$.