Elearning CodePath – CTP Online Judge

Đếm Xâu Con Chia hết

STRINGS

### 📌 Thông tin chung

| Mục | Chi tiết |
### 📝 Bài toán

Cho một xâu $S$ độ dài $N$, trong đó mỗi ký tự là một chữ số từ '0' đến '9'.
Cho một số nguyên tố $P$.

Yêu cầu: Đếm số lượng **xâu con liên tiếp** (subarray) của $S$ mà khi ghép các chữ số lại sẽ tạo thành một số nguyên chia hết cho $P$.

Lưu ý:
1. Xâu con liên tiếp bắt đầu bởi chữ số '0' cũng được tính vào kết quả.
2. Hai xâu con được coi là phân biệt nếu chúng bắt đầu hoặc kết thúc ở hai vị trí khác nhau trong xâu ban đầu. Tức là ta đếm số lượng cặp chỉ số $(l, r)$ ($1 \le l \le r \le N$) thỏa mãn điều kiện.

Nếu $S[l..r]$ là xâu con, số nguyên tương ứng $V(l, r)$ phải thỏa mãn:
$$
V(l, r) \equiv 0 \pmod{P}
$$

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

* Dòng 1: Hai số nguyên $N$ và $P$.
* Dòng 2: Một xâu chứa $N$ kí tự.

Giới hạn: $1 \le N \le 2 \times 10^5$, $2 \le P \le 10000$.

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

In ra một số nguyên duy nhất là số lượng xâu con liên tiếp thỏa mãn điều kiện.

---
### ✨ Ví dụ

| Input (`STRINGS.inp`) | Output (`STRINGS.out`) |
| :--- | :--- |
| `4 3` <br> `1234` | `4` |
| `20 11` <br> `00112233445566778899` | `66` |

✅ Đã AC: 0 / 3 submissions