Elearning CodePath – CTP Online Judge

Chia cho 11 (DIV11)

DIV11

🟢 Hard #Math #Number Theory #Combinatorics #Interval

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho dãy số nguyên gồm N phần tử A1, A2, ..., AN, trong đó mỗi Ai là một chữ số (0 <= Ai < 10).
Yêu cầu: Đếm số lượng cặp chỉ số (i, j) thỏa mãn đồng thời các điều kiện sau:
1. 1 <= i < j <= N.
2. Giá trị của biểu thức A_i0A_j * (Ai - Aj) chia hết cho 11.

Lưu ý: A_i0A_j là số tự nhiên được ghép bởi chữ số Ai, chữ số 0 và chữ số Aj (ví dụ: Ai = 5, Aj = 6 thì A_i0A_j = 506).

---

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

Dữ liệu vào từ file DIV11.INP:
* Dòng đầu tiên chứa một số nguyên dương N (1 <= N <= 10^5).
* Dòng thứ hai chứa N chữ số A1, A2, ..., AN (0 <= Ai < 10), các số cách nhau bởi dấu cách.

---

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

Ghi ra file DIV11.OUT một số nguyên duy nhất là số lượng cặp (i, j) tìm được.

---

### ✨ Ví dụ

| Input | Output |
| :--- | :--- |
| 2 <br> 5 6 | 1 |

Giải thích ví dụ:
* i = 1, j = 2: Ai = 5, Aj = 6.
* Biểu thức: 506 * (5 - 6) = 506 * (-1) = -506.
* Vì -506 chia hết cho 11 (-506 = 11 * -46) nên cặp (1, 2) thỏa mãn.

---

### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | N <= 2000 | 30% |
| 2 | N <= 10^5 | 70% |

✅ Đã AC: 3 / 11 submissions