Xâu đặc biệt 2

Nguồn: CLUE OJ – Map/Set Độ khó: Khá Tiền tố map<vector<int>, int>

Đề bài

Cho một chuỗi có độ dài $n$ gồm các chữ cái tiếng Anh. Gọi số lượng kí tự phân biệt trong chuỗi này là $k$. Một xâu con (các kí tự liền kề) được gọi là đặc biệt nếu $k$ ký tự khác nhau trong xâu con xuất hiện với số lần bằng nhau.

Viết chương trình đếm số xâu con đặc biệt trong chuỗi đã cho. Kết quả được chia lấy dư cho $10^9 + 7$.

Dữ liệu:

Dòng 1: chứa một số nguyên $n$ $(2 \le n \le 10^5)$ – số ký tự trong chuỗi.
Dòng 2: chứa một chuỗi $n$ ký tự, gồm các chữ cái tiếng Anh in hoa và in thường. Lưu ý rằng các chữ in hoa và in thường là khác nhau (ví dụ A và a là khác nhau).

Kết quả: dòng 1 ghi số lượng xâu con đặc biệt, chia lấy dư cho $10^9 + 7$.

Giới hạn: thời gian 1 giây, bộ nhớ 128 MB.

Subtask: 50% điểm đầu tiên với $n \le 10^3$; 50% điểm còn lại không có giới hạn gì thêm.

Thầy giải thích lại đề: đầu tiên xác định toàn bộ chuỗi có $k$ ký tự phân biệt (tức là tìm ra $k$ là bao nhiêu). Như ví dụ 1 thì $k = 3$ (chỉ gồm 3 ký tự a, b, c). Rồi ta tìm tất cả các chuỗi con sao cho chuỗi con đó có đúng $k$ ký tự phân biệt bên trong (đủ cả $k$ ký tự đã tìm được), và số lần xuất hiện của mỗi ký tự trong chuỗi con đó đều phải bằng nhau. Ví dụ 1 có 4 chuỗi con thoả mãn:

Vị trí 1 → 3: abc (đủ 3 ký tự a, b, c, mỗi ký tự xuất hiện 1 lần).
Vị trí 1 → 6: abccba (mỗi ký tự xuất hiện 2 lần).
Vị trí 4 → 6: cba (mỗi ký tự xuất hiện 1 lần).
Vị trí 6 → 8: abc (mỗi ký tự xuất hiện 1 lần).

Ví dụ 1 – input

8
abccbabc

Ví dụ 1 – output

Ví dụ 2 – input

7
abcABCC

Ví dụ 2 – output

Ví dụ 3 – input

20
SwSSSwwwwSwSwwSwwwwS

Ví dụ 3 – output

Giải thích ví dụ 2: abcABCC có $k = 6$ ký tự phân biệt; chỉ có chuỗi abcABC (vị trí 1 → 6) chứa đủ 6 ký tự, mỗi ký tự 1 lần.

Lời mở đầu

Đề hơi khó hiểu lúc đầu, nhưng sau khi "dịch" lại thì đây là một bài đếm xâu con rất đẹp. Cách vét cạn $O(n^2)$ khá dễ, còn để chạy $n = 10^5$ ta cần một mẹo quen thuộc: biến điều kiện của đoạn $[l, r]$ thành điều kiện "hai tiền tố giống nhau", rồi dùng map đếm số cặp tiền tố giống nhau.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

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ộ test100 test, 2 subtask Cách 1Vét cạn O(n²k)Ý tưởngDấu vân tay tiền tố Cách 2map vector Tổng kếtKết quả chạy thật

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

Bộ test có 100 test:

Test	n	k (số ký tự phân biệt)	Kiểu chuỗi	Đáp án
1–20	2 – 20	1 – 6	ngẫu nhiên, nhỏ	0 – 24
21–27	1.000	10	ngẫu nhiên 10 chữ a–e, A–E	0 – 6
28–50	1.000	4	ngẫu nhiên 4 chữ a, b, A, B	176 – 328
51–69	100.000	4	ngẫu nhiên 4 chữ a, b, A, B	83.329 – 84.450
70–100	100.000	22 – 52	lặp lại chu kỳ "abc…" gồm k chữ	96.105.771 – 227.227.275

Có 5 test chỉ gồm 1 loại ký tự ($k = 1$, test 4, 8, 9, 10, 14): khi đó mọi xâu con đều đặc biệt, đáp án là $n(n+1)/2$.
Có test đáp án bằng 0 (test 1, 21).
Test 70–100 là chuỗi lặp lại abcd… theo chu kỳ $k$ chữ ($k$ giảm dần từ 52 xuống 22): mọi xâu con có độ dài là bội của $k$ đều đặc biệt, nên đáp án rất lớn. Đáp án lớn nhất trong bộ test là 227.227.275, vẫn nhỏ hơn $10^9 + 7$, nên thực tế phép chia lấy dư chưa bao giờ "có tác dụng". Nhưng về lý thuyết đáp án có thể tới $n(n+1)/2 \approx 5 \cdot 10^9$, nên vẫn phải dùng long long và lấy dư.

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

Cách 1Vét cạn mọi xâu con – O(n² · k)

Với mỗi điểm đầu $l$, ta mở rộng dần điểm cuối $r$ và cập nhật mảng đếm cnt. Sau mỗi lần thêm $s[r]$ ta kiểm tra xem $k$ ký tự có cùng số lần xuất hiện không, bằng cách so từng ký tự với ký tự đầu tiên ch[0].

C++▶ Chạy tay từng dòng codeCách 1: thử mọi xâu con, cập nhật mảng đếm và so k ký tự với ký tự đầu.

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

Dữ liệu mẫu:

Vì so sánh cả $k$ ký tự của chuỗi gốc, nếu xâu con thiếu ký tự nào (đếm = 0) mà ký tự khác có mặt thì sẽ khác nhau → không đếm. Còn trường hợp "tất cả đều bằng 0" không xảy ra vì xâu con luôn có ít nhất 1 ký tự.
Mảng cnt[128] đánh số theo mã ASCII nên dùng trực tiếp cnt[s[r]] cho cả chữ hoa lẫn chữ thường.

Không gian$O(n)$

Thời gian$O(n^2 \cdot k)$

Kết quả chạy thật: bản C++ đúng 50/100 test (Subtask 1: 50/50, Subtask 2: 0/50). Subtask 1 chạy tối đa 0.01 giây; với $n = 10^5$ thì $n^2/2 = 5 \cdot 10^9$ cặp $(l, r)$, quá thời gian toàn bộ subtask 2.

Ý tưởngĐoạn đặc biệt = hai tiền tố có cùng "dấu vân tay"

Gọi $P_c(i)$ là số lần ký tự $c$ xuất hiện trong $i$ ký tự đầu tiên của chuỗi (tiền tố độ dài $i$, $P_c(0) = 0$). Xâu con $s[l..r-1]$ (từ vị trí $l$ đến $r - 1$, đánh số từ 0) chứa ký tự $c$ đúng $P_c(r) - P_c(l)$ lần. Xâu con đặc biệt khi các số này bằng nhau với mọi $c$, tức là với $c_0$ là ký tự đầu tiên:

$P_c(r) - P_c(l)$ $= P_{c_0}(r) - P_{c_0}(l) \iff P_c(r) - P_{c_0}(r)$ $= P_c(l) - P_{c_0}(l)$ với mọi $c$.

Dấu vân tay của tiền tố

Với mỗi tiền tố $i$, lập vector $d(i) = \big(P_{c_1}(i) - P_{c_0}(i),\ \ldots,\ P_{c_{k-1}}(i) - P_{c_0}(i)\big)$ gồm $k - 1$ số. Xâu con $s[l..r-1]$ đặc biệt $\iff d(l) = d(r)$. Đáp án = số cặp $l < r$ có $d(l) = d(r)$.

Nếu $d(l) = d(r)$ thì mọi ký tự xuất hiện cùng $t$ lần trong xâu con, và độ dài xâu con là $k \cdot t > 0$ nên $t \ge 1$: xâu con tự động chứa đủ cả $k$ ký tự. Rất gọn!

Đếm số cặp bằng nhau thì quen rồi: duyệt $i$ từ trái sang phải, cộng vào đáp án số tiền tố trước đó có cùng vector (lưu trong map<vector<int>, int>), rồi tăng đếm của vector hiện tại. Nhớ đưa tiền tố rỗng $d(0) = (0, \ldots, 0)$ vào map từ đầu. Em nhập chuỗi rồi bấm Tiếp để xem:

Chuỗi:

Ví dụ nhanh:

Cách 2map<vector<int>, int> đếm tiền tố – O(n · k · log n)

C++▶ Chạy tay từng dòng codeCách 2: vector chênh lệch d của từng tiền tố, map đếm số tiền tố cùng d.

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

Dữ liệu mẫu:

id[c] đánh số các ký tự phân biệt theo thứ tự xuất hiện $0, 1, \ldots, k-1$, nên ký tự số 0 chính là $c_0$.
mp[d] = 1 trước vòng lặp chính là tiền tố rỗng: nhờ nó mà các xâu con bắt đầu từ vị trí 0 (như abc, abccba ở ví dụ 1) được đếm.
ans += mp[d] phải đứng trước mp[d]++, để không ghép tiền tố $i$ với chính nó.
Khi $k = 1$ thì vector d rỗng, mọi tiền tố đều giống nhau, đáp án là $0 + 1 + 2 + \cdots + n = n(n+1)/2$ – đúng như mong đợi.
So sánh 2 vector trong map tốn $O(k)$, mỗi thao tác map có $O(\log n)$ lần so sánh. Với $n = 10^5$, $k \le 52$ là khoảng $10^8$ phép tính đơn giản – vẫn kịp.

Không gian$O(n \cdot k)$

Thời gian$O(n \cdot k \cdot \log n)$

Kết quả chạy thật: bản C++ đúng 100/100 test (Subtask 1: 50/50, Subtask 2: 50/50). Test lâu nhất mất 0.06 giây (thời gian CPU).

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

Mình chấm cả 2 cách (C++ và Python) trên toàn bộ 100 test với giới hạn 1 giây, đo thời gian CPU (máy chấm của mình lúc chạy đang khá tải):

Lời giải	Subtask 1 test 1–50	Subtask 2 test 51–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	50/50	0/50	50/100	0.01s
Cách 1 – Python	50/50	0/50	50/100	0.43s
Cách 2 – C++	50/50	50/50	100/100	0.06s
Cách 2 – Python	50/50	50/50	100/100	0.64s

Ghi chú của mình: cách 2 đạt trọn 100% test. Python: cách 1 đúng 50/100, cách 2 đúng 100/100 test; bản Python cách 2 dùng tuple làm khoá của dict (vì list không băm được). Nếu muốn nhanh hơn nữa có thể thay map bằng unordered_map với hàm băm cho vector, nhưng ở bài này map là đủ.

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 😇

Lập Trình Thuật Toán