Elearning CodePath – CTP Online Judge

Chia mảng thành hai phần có tổng bằng nhau

HASH002

🟢 Hard #Hash #Dynamic Programming #Prefix Sum #Interval

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho dãy số $A$. Đếm số cách chia mảng thành hai phần có tổng bằng nhau. Bao gồm cả những cách chia trùng lặp.

---
### 📥 Định dạng Đầu vào

* Dòng đầu tiên là số nguyên $N$ — độ dài của mảng ($1 \le N \le 10^5$).
* Dòng thứ hai gồm $N$ số nguyên $A_1, A_2, \dots, A_N$ ($-10^9 \le A_i \le 10^9$).

---
### 📤 Định dạng Đầu ra

Một số nguyên duy nhất — số lượng cặp đoạn con $(A', A'')$ có tổng bằng nhau. Hoặc in ra $\mathbf{-1}$ nếu không chia được (tức là tổng toàn bộ mảng là số lẻ, hoặc không tìm được tập con thỏa mãn).

---
### ✨ Ví dụ

| Dữ liệu vào | Dữ liệu ra |
| :---: | :---: |
| `4` <br> `1 2 1 2` | `4` |

**Giải thích Ví dụ:**
Tổng mảng là $6$. Mục tiêu là tìm tập con có tổng $3$.
Các tập con có tổng $3$ là: $\{A_1, A_3\}$, $\{A_1, A_4\}$, $\{A_2, A_3\}$, $\{A_2, A_4\}$. Tổng cộng 4 cách.

---
### 🏷 Ràng buộc

| Subtask | Ràng buộc $N$ | Ràng buộc $A_i$ | Tỷ lệ điểm |
| :--- | :--- | :--- | :--- |
| $1$ | $1 \le N \le 500$ | $abs(A_i) \le 10^9$ | $30\%$ |
| $2$ | $500 < N \le 10^3$ | $abs(A_i) \le 10^9$ | $30\%$ |
| $3$ | $1000 < N \le 10^5$ | $abs(A_i) \le 10^9$ | $40\%$ |

---

✅ Đã AC: 0 / 9 submissions