Đếm xâu con chia hết cho p

Nguồn: CLUE OJ – Chương 45: Đồng dư modulo Độ khó: Khá Đồng dư Hậu tố Đếm cặp

Đề bài

Bạn được cho một xâu độ dài $n$, mỗi kí tự trong xâu là một chữ số từ '0' đến '9'.

Bạn cũng được cho một số nguyên tố $P$. Hãy đếm xem trong xâu ban đầu có bao nhiêu xâu con liên tiếp mà khi ghép các chữ số ở từng vị trí lại sẽ tạo thành một số chia hết cho $P$.

Lưu ý: xâu con liên tiếp bắt đầu bởi chữ số '0' cũng được tính. Hai xâu con liên tiếp được xem 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.

Dữ liệu:

• Dòng đầu tiên gồm hai số nguyên $n$ và $P$ $(1 \le n \le 2 \cdot 10^5,\ 2 \le P \le 10\,000)$ – số kí tự của xâu và số nguyên tố $P$.
• Dòng tiếp theo gồm một xâu chứa $n$ kí tự.

Kết quả: in ra một số nguyên duy nhất là số xâu con liên tiếp tạo thành số chia hết cho $P$.

Subtask: $50\%$ số test có $n \le 5000$; $50\%$ số test còn lại không có ràng buộc gì thêm.

Ví dụ 1 – input

4 3
1234

Ví dụ 1 – output

4

Ví dụ 2 – input

20 11
00112233445566778899

Ví dụ 2 – output

66

Giải thích ví dụ 1: các xâu con chia hết cho $3$ là 12, 3, 123, 234 – có $4$ xâu.

Lời mở đầu

Có tới $\frac{n(n+1)}{2} \approx 2 \cdot 10^{10}$ xâu con, nên không thể xét từng xâu. Bí quyết là nhìn mỗi xâu con như hiệu của hai hậu tố, rồi dùng đồng dư để biến bài toán thành "đếm cặp hậu tố có cùng số dư". Bài còn một cái bẫy rất hay: khi $P = 2$ hoặc $P = 5$ thì mẹo này sai, và mình sẽ chỉ ra tại sao.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test40 test, 2 mứcÝ tưởnghiệu hai hậu tốCách 1duyệt O(n²)Cách 2đếm cặp – có bẫyCách 3xử lý p = 2, 5Tổng kếtkết quả chạy thật

Bộ testBộ test chính thức có gì?

Bộ test có 40 test (tệp input.000 … input.039, mình đánh số 1 – 40):

Test	$n$	$P$	Đáp án
1 – 5	294 – 299	2, 19, 11, 3, 13	2 274 – 21 708
6 – 10	4 908 – 4 996	19, 17, 5, 19, 17	635 601 – 2 568 664
11 – 15	659 – 3 526	2, 2, 2, 2, 5	105 584 – 3 079 848
16 – 20	5 000	283 – 7 517	2 248 – 44 776
21 – 40	199 905 – 200 000	2, 3, 5, 7, 991 … 9 533	tới 20 000 100 000

• Có tới 15 test với $P = 2$ hoặc $P = 5$ (test 1, 8, 11–15, 26–32, 34) – đúng chỗ cái bẫy của bài.
• Test 30 ($P = 2$, xâu chỉ toàn chữ số chẵn) và test 31 ($P = 5$, xâu chỉ có chữ số 0 và 5) có mọi xâu con đều chia hết, đáp án là $\frac{n(n+1)}{2}$; test 31 có $n = 200\,000$ nên đáp án $20\,000\,100\,000$ – vượt int, phải dùng long long.

Subtask	Điều kiện	Các test	Cách ăn được
1 (50%)	$n \le 5000$	1 – 20	Cách 1, 3
2 (50%)	$n \le 2 \cdot 10^5$	21 – 40	Cách 3

Ý tưởngXâu con = hiệu hai hậu tố

Gọi $suf_i$ là giá trị số của hậu tố $s[i..n-1]$ (quy ước $suf_n = 0$ – hậu tố rỗng). Xâu con $s[l..r]$ "dịch" sang trái đúng $n-1-r$ chữ số chính là phần chênh lệch giữa hai hậu tố:

Công thức

$$\overline{s_l s_{l+1} \ldots s_r} \cdot 10^{\,n-1-r} = suf_l - suf_{r+1}$$

Ví dụ xâu 1234: $suf_1 = 234$, $suf_3 = 4$, và $\overline{23} \cdot 10^1 = 230 = 234 - 4$. Đúng!

Nếu $P$ không chia hết $10$ (tức $P \ne 2, 5$) thì $\gcd(10^k, P) = 1$, nên nhân với $10^{n-1-r}$ không làm thay đổi tính chia hết:

Đồng dư

$$P \mid \overline{s_l \ldots s_r} \iff P \mid (suf_l - suf_{r+1}) \iff suf_l \equiv suf_{r+1} \pmod P$$

Vậy đáp án = số cặp $(l, r+1)$ với $l < r+1$ mà hai hậu tố có cùng số dư khi chia cho $P$. Duyệt $i$ từ $n-1$ về $0$, tính $suf_i \bmod P$ (cộng thêm chữ số $s_i \cdot 10^{n-1-i}$), mỗi lần cộng vào đáp án số hậu tố đã gặp có cùng số dư.

Còn $P = 2$ hoặc $5$? Khi đó $10^k$ chia hết cho $P$ nên mọi hiệu đều "giả" chia hết – công thức trên sai. Nhưng bù lại, một số chia hết cho $2$ (hay $5$) chỉ phụ thuộc chữ số cuối: nếu $s_r$ chia hết cho $P$ thì cả $r+1$ xâu con kết thúc tại $r$ đều chia hết.

Em nhập xâu và $P$ (là số nguyên tố khác 2, 5) rồi bấm Tiếp để xem bảng số dư của các hậu tố:

Xâu: P =

Ví dụ nhanh:

Cách 1Duyệt mọi xâu con – O(n²)

Cố định điểm đầu $l$, kéo dài $r$ dần sang phải và cập nhật số dư theo kiểu "Horner": $rem = (rem \cdot 10 + s_r) \bmod P$. Không bao giờ phải tạo ra số thật (có thể dài tới $2 \cdot 10^5$ chữ số).

C++▶ Chạy tay từng dòng codeCách 1: mỗi điểm đầu l, kéo dài r và cập nhật rem = (rem·10 + chữ số) % p.

Dữ liệu vào (stdin) – sửa thoải mái4 3 1234

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi bước chỉ là một phép nhân, cộng, chia lấy dư trên số nhỏ ($rem < P \le 10^4$).
• Tổng số bước là $\frac{n(n+1)}{2}$: với $n = 5000$ khoảng $1{,}25 \cdot 10^7$ – chạy tức thì; với $n = 2 \cdot 10^5$ khoảng $2 \cdot 10^{10}$ – quá chậm.
• Cách này đúng với mọi $P$ kể cả $2$ và $5$, nên mình dùng nó để kiểm tra các cách sau.

Không gian$O(n)$

Thời gian$O(n^2)$

Kết quả chạy thật: bản C++ đúng 20/40 test (Subtask 1: 20/20, lâu nhất 0,137 giây; Subtask 2: 0/20 – quá thời gian). Bản Python chậm hơn nhiều, chỉ đúng 9/40 (các test có $n \le 2003$; từ $n = 3526$ trở lên đã quá 1 giây).

Cách 2Đếm cặp hậu tố cùng số dư – O(n + P) nhưng có bẫy

Làm đúng theo phần Ý tưởng: duyệt $i$ từ phải sang trái, giữ $suf = suf_i \bmod P$ và $pw = 10^{n-1-i} \bmod P$. Mảng cntRem[x] đếm số hậu tố đã gặp có số dư $x$ (ban đầu có hậu tố rỗng, số dư $0$).

C++▶ Chạy tay từng dòng codeCách 2: duyệt từ phải sang trái, đếm các hậu tố trước đó có cùng số dư suf.

Dữ liệu vào (stdin) – sửa thoải mái4 3 1234

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi chữ số xử lý trong $O(1)$, mảng cntRem có $P \le 10^4$ phần tử – cực nhanh.
• cnt phải là long long: đáp án có thể tới $\frac{n(n+1)}{2} \approx 2 \cdot 10^{10}$.
• Cái bẫy: em chọn dữ liệu mẫu "P = 2 (sai!)" với xâu 12345: đáp án đúng là $6$ (12, 2, 1234, 234, 34, 4), nhưng cách 2 in ra $10$. Lý do: với $P = 2$, $pw = 10^k \bmod 2 = 0$ ngay từ $k \ge 1$, nên mọi hậu tố dài từ 2 trở lên đều có "số dư" chỉ do chữ số cuối quyết định – điều kiện $\gcd(10, P) = 1$ trong phần Ý tưởng bị vi phạm.

Không gian$O(n + P)$

Thời gian$O(n + P)$

Kết quả chạy thật: bản C++ đúng 27/40 test (Subtask 1: 13/20, Subtask 2: 14/20), chạy lâu nhất chỉ 0,008 giây. Sai đúng 13 test có $P = 2$ hoặc $P = 5$; hai test 30, 31 cũng có $P = 2, 5$ nhưng "may mắn" đúng vì mọi xâu con đều chia hết. Bản Python cũng đúng 27/40.

Cách 3Tách riêng P = 2, 5 – full điểm

Thêm một nhánh cho $P = 2$ hoặc $P = 5$: số chia hết cho $2$ (hay $5$) khi và chỉ khi chữ số cuối chia hết cho $2$ (hay $5$). Nếu $s_r$ chia hết thì mọi xâu con kết thúc tại $r$ – có $r + 1$ xâu (điểm đầu $0, 1, \ldots, r$) – đều được đếm. Các $P$ còn lại giữ nguyên cách 2.

C++▶ Chạy tay từng dòng codeCách 3: p = 2, 5 thì nhìn chữ số cuối; p khác thì đếm cặp hậu tố cùng số dư.

Dữ liệu vào (stdin) – sửa thoải mái5 2 12345

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Nhánh $P = 2, 5$ chạy $O(n)$, nhánh còn lại $O(n + P)$.
• Bài học: mẹo "chia hết ⇔ cùng số dư" chỉ đúng khi được phép bỏ đi thừa số $10^k$, tức là khi $\gcd(10, P) = 1$. Đề cho $P$ nguyên tố nên chỉ có hai ngoại lệ là $2$ và $5$.

Không gian$O(n + P)$

Thời gian$O(n + P)$

Kết quả chạy thật: bản C++ đúng 40/40 test, lâu nhất 0,008 giây; bản Python đúng 40/40, lâu nhất 0,152 giây.

Tổng kếtKết quả chạy thật trên bộ test

Mình chấm cả 3 cách (C++ và Python) trên toàn bộ 40 test với giới hạn 1 giây, đo thời gian CPU:

Lời giải	Subtask 1 test 1–20	Subtask 2 test 21–40	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	20/20	0/20	20/40	0,137s
Cách 1 – Python	9/20	0/20	9/40	0,451s
Cách 2 – C++	13/20	14/20	27/40	0,008s
Cách 2 – Python	13/20	14/20	27/40	0,165s
Cách 3 – C++	20/20	20/20	40/40	0,008s
Cách 3 – Python	20/20	20/20	40/40	0,152s

Ghi chú của mình: cách 1 chỉ quá thời gian chứ không sai; cách 2 thì ngược lại – siêu nhanh nhưng sai kết quả ở các test $P = 2, 5$. Bộ test cố tình có tới 15 test như vậy, nên quên trường hợp đặc biệt là mất gần một phần ba số điểm. Cách 3 ghép cả hai ý: full điểm cả C++ lẫn Python.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇