Bảng hiệu kiêng (Đề tự luyện HSG Tin 12 – Bài 3)
Đề bài
Bảng hiệu kiêng. Cho xâu $S$ ($n$ chữ) và xâu cấm $P$ ($m$ chữ), đều gồm chữ cái thường. Đếm số cách chọn một tập khác rỗng các vị trí của $S$ (giữ nguyên thứ tự) sao cho dòng chữ thu được không chứa $P$ như một đoạn liên tiếp. Hai cách khác nhau nếu tập vị trí khác nhau. In kết quả modulo $10^9 + 7$.
Dữ liệu vào: dòng 1 là $S$ ($1 \le n \le 10^5$), dòng 2 là $P$ ($1 \le m \le 100$).
Kết quả: số cách chọn hợp lệ modulo $10^9 + 7$.
- Subtask 1 (20%): $n \le 20$.
- Subtask 2 (30%): các chữ cái của $P$ đôi một khác nhau.
- Subtask 3 (50%): không có ràng buộc gì thêm.
lolo
lo7Hợp lệ: 4 cách chọn một chữ, cùng ll (vị trí 1, 3), ol (2, 3), oo (2, 4). Mọi cách khác đều chứa lo.
ababa
aba2231 cách chọn trừ đi 9 cách chứa aba: 4 cách ra đúng aba và abab, abaa, aaba, baba, ababa.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Bảng hiệu kiêngLời mở đầu
Có $2^n - 1$ cách chọn, nên với $n = 10^5$ không thể thử hết. Ta cần một cách "nén" thông tin. Hãy tưởng tượng thầy Sơn đi dọc dải chữ từ trái sang phải. Tới mỗi chữ, thầy quyết định lấy hoặc bỏ, và dòng chữ trên bảng hiệu dài dần ở phía cuối. Câu hỏi then chốt:
Từ đó có QHĐ: $dp[q]$ là số cách chọn (trong phần đã duyệt) có trạng thái $q$. Gặp chữ $c$: bỏ $c$ thì trạng thái giữ nguyên; lấy $c$ thì trạng thái chuyển sang $go(q, c)$. Toàn bộ độ khó là tính đúng $go(q, c)$ – "đang khớp $q$ chữ, ghép thêm $c$ thì khớp bao nhiêu?". Đây chính là automaton của thuật toán KMP:
Hình 1. Automaton của $P$ = aab. Mũi tên xanh là khớp tiếp. Mũi tên cam là chỗ dễ sai: đang khớp aa mà gặp thêm a thì ba chữ cuối là aaa, vẫn khớp được aa (trạng thái 2) chứ không phải quay về 1. Tới trạng thái 3 là cấm.
Cách 1Quay lui có cắt nhánh – O(2ⁿ · m) · 20%
Với $n \le 20$, ta thử mọi cách: hàm go(i) xét chữ $s_i$, gọi đệ quy hai nhánh bỏ và lấy. Mẹo cắt nhánh: mỗi khi vừa ghép thêm một chữ, chỉ cần kiểm tra $m$ chữ cuối của dòng chữ có bằng $P$ không. Lần đầu tiên $P$ xuất hiện thì nó phải nằm ở cuối dòng chữ. Nếu có thì dừng nhánh đó luôn (mọi cách mở rộng tiếp đều chứa $P$). Đến cuối xâu thì đếm 1 cách. Kết quả cuối cùng trừ đi 1 vì cách chọn rỗng cũng được đếm.
Bản Python dùng ngăn xếp thay cho đệ quy (độ sâu chỉ 20 nhưng gọi hàm trong Python khá chậm).
#include <bits/stdc++.h>
using namespace std;
string s, p, t; // t: dong chu dang ghep
long long cnt = 0;
// dang xet chu s[i]
void go(int i) {
int m = p.size(), k = t.size();
if (k >= m && t.compare(k - m, m, p) == 0) return; // vua tao ra P: cat nhanh
if (i == (int)s.size()) { cnt++; return; }
go(i + 1); // bo chu s[i]
t.push_back(s[i]); // lay chu s[i]
go(i + 1);
t.pop_back();
}
int main() {
cin >> s >> p;
go(0);
cout << (cnt - 1) % 1000000007 << "\n"; // bo cach chon rong
return 0;
}import sys
def main():
data = sys.stdin.read().split()
s, p = data[0], data[1]
n = len(s)
cnt = 0
t = [] # dong chu dang ghep
# ngan xep thay cho de quy: (i, buoc) voi buoc 0 = vua vao, 1 = da bo s[i], 2 = da lay s[i]
st = [(0, 0)]
while st:
i, b = st.pop()
if b == 0:
if len(t) >= len(p) and "".join(t[-len(p):]) == p:
continue # vua tao ra P: cat nhanh
if i == n:
cnt += 1
continue
st.append((i, 1)); st.append((i + 1, 0)) # bo chu s[i]
elif b == 1:
t.append(s[i])
st.append((i, 2)); st.append((i + 1, 0)) # lay chu s[i]
else:
t.pop()
print((cnt - 1) % 1000000007) # bo cach chon rong
main()Cách 2QHĐ khi P không có chữ lặp – O(n · m) · 50%
Khi các chữ của $P$ đôi một khác nhau, hàm chuyển trạng thái rất đơn giản. Đang khớp $q$ chữ, ghép thêm $c$:
- Nếu $c = P[q]$: khớp tiếp, sang trạng thái $q + 1$.
- Ngược lại, nếu $c = P[0]$: sang trạng thái $1$; còn không thì về $0$.
Vì sao đúng? Giả sử sau khi ghép $c$, phần cuối khớp $k \ge 2$ chữ đầu của $P$. Khi đó chữ cuối là $c = P[k-1]$ và chữ áp cuối là $P[q-1] = P[k-2]$. Vì $P$ không lặp chữ nên $k - 2 = q - 1$, tức $k = q + 1$ và $c = P[q]$ – rơi vào trường hợp đầu. Vậy khi lệch thì chỉ có thể khớp lại tối đa 1 chữ.
Đây là QHĐ $dp[q]$ ở Lời mở đầu với hàm chuyển đơn giản. Mỗi chữ của $S$ mất $O(m)$, tổng $O(n \cdot m)$. Để lấy trọn 50% điểm, code kiểm tra: nếu $P$ có chữ lặp thì quay về quay lui của Cách 1 (subtask 1 có $n \le 20$).
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
string s, p, t;
long long cnt = 0;
void back(int i) { // quay lui cua Cach 1 (dung khi n <= 20)
int m = p.size(), k = t.size();
if (k >= m && t.compare(k - m, m, p) == 0) return;
if (i == (int)s.size()) { cnt++; return; }
back(i + 1);
t.push_back(s[i]);
back(i + 1);
t.pop_back();
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> s >> p;
int n = s.size(), m = p.size();
if (set<char>(p.begin(), p.end()).size() < p.size()) { // P co chu lap
back(0);
cout << (cnt - 1) % MOD << "\n";
return 0;
}
vector<long long> dp(m, 0), nd(m); // dp[q]: so cach chon dang khop q ky tu
dp[0] = 1;
for (int i = 0; i < n; i++) {
nd = dp; // khong lay chu s[i]
for (int q = 0; q < m; q++) {
int t; // lay chu s[i]: P khong co chu lap
if (s[i] == p[q]) t = q + 1; // khop tiep
else if (s[i] == p[0]) t = 1; // lech: chi co the khop lai chu dau
else t = 0;
if (t < m) nd[t] = (nd[t] + dp[q]) % MOD;
}
swap(dp, nd);
}
long long ans = 0;
for (int q = 0; q < m; q++) ans = (ans + dp[q]) % MOD;
cout << (ans - 1 + MOD) % MOD << "\n";
return 0;
}import sys
MOD = 1000000007
def back(s, p): # quay lui cua Cach 1 (dung khi n <= 20)
n = len(s); cnt = 0; t = []
st = [(0, 0)]
while st:
i, b = st.pop()
if b == 0:
if len(t) >= len(p) and "".join(t[-len(p):]) == p:
continue
if i == n:
cnt += 1
continue
st.append((i, 1)); st.append((i + 1, 0))
elif b == 1:
t.append(s[i])
st.append((i, 2)); st.append((i + 1, 0))
else:
t.pop()
return cnt
def main():
data = sys.stdin.read().split()
s, p = data[0], data[1]
m = len(p)
if len(set(p)) < m: # P co chu lap
print((back(s, p) - 1) % MOD)
return
dp = [0] * m # dp[q]: so cach chon dang khop q ky tu
dp[0] = 1
for ch in s:
nd = dp[:] # khong lay chu nay
for q in range(m): # lay chu nay: P khong co chu lap
if ch == p[q]:
t = q + 1 # khop tiep
elif ch == p[0]:
t = 1 # lech: chi co the khop lai chu dau
else:
t = 0
if t < m:
nd[t] += dp[q]
dp = [x % MOD for x in nd]
print((sum(dp) - 1) % MOD)
main()aab, $S$ = aaab: đáp án đúng là 11 (15 cách trừ 4 cách chứa aab). Công thức "lệch thì về 0 hoặc 1" cho rằng aa + a chỉ còn khớp 1 chữ. Vì thế nó coi cách chọn cả 4 chữ (aaab) là hợp lệ và in ra 12. Bộ test subtask 3 bắt đúng lỗi này ở mọi test.Cách 3QHĐ + automaton KMP – O(26·m + n·m) · 100%
Với $P$ tổng quát, ta tính bảng $go[q][c]$ một lần bằng mảng fail (prefix function) của KMP:
- $fail[i]$ = độ dài biên dài nhất của $P[0..i-1]$, tức xâu vừa là tiền tố vừa là hậu tố (khác chính nó). Tính theo kiểu KMP quen thuộc trong $O(m)$.
- $go[q][c] = q + 1$ nếu $P[q] = c$. Ngược lại, $go[0][c] = 0$ và $go[q][c] = go[fail[q]][c]$ với $q \ge 1$. Ý nghĩa: không khớp tiếp được thì thử với biên dài nhất của phần đang khớp. Vì $fail[q] < q$, hàng đó đã tính xong nên bảng điền được trong $O(26 \cdot m)$.
Với $P$ = aab: $fail = [0, 0, 1, 0]$. Hàng $q = 2$ (đang khớp aa), chữ a: $P[2] = $ b $\ne$ a nên $go[2][a] = go[fail[2]][a] = go[1][a] = 2$ – đúng như Hình 1.
Chạy tay $S$ = aaab, $P$ = aab ($go[0] = \{a{:}1, b{:}0\}$, $go[1] = \{a{:}2, b{:}0\}$, $go[2] = \{a{:}2, b{:}3✗\}$):
| Sau chữ | dp[0] | dp[1] | dp[2] | Giải thích |
|---|---|---|---|---|
| (đầu) | 1 | 0 | 0 | chỉ có cách chọn rỗng |
| a | 1 | 1 | 0 | lấy a: 0→1 |
| a | 1 | 2 | 1 | lấy a: 0→1, 1→2 |
| a | 1 | 3 | 4 | lấy a: 0→1, 1→2, 2→2 |
| b | 5 | 3 | 4 | lấy b: 0→0, 1→0, 2→3 (cấm, bỏ) |
Tổng $5 + 3 + 4 = 12$, trừ cách chọn rỗng được 11 ✓. Mỗi phép cộng lấy modulo $10^9 + 7$, và nhớ cộng thêm MOD trước khi lấy dư khi trừ 1.
Các bạn thử nhập $S$, $P$ bất kỳ để xem bảng go và mảng dp thay đổi:
Bản Python giữ nguyên ý tưởng, chỉ tăng tốc vòng QHĐ: với mỗi chữ $c$, đa số trạng thái chuyển về 0. Vì vậy ta chỉ lưu danh sách các cặp $(q, go[q][c])$ có $go \ne 0$, còn phần về 0 thì tính bằng tổng trừ đi. Code C++ dưới đây là bản đã kiểm chứng.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
string s, p;
cin >> s >> p;
int n = s.size(), m = p.size();
// fail[i]: do dai bien dai nhat (vua la tien to vua la hau to) cua p[0..i-1]
vector<int> fail(m + 1, 0);
for (int i = 1; i < m; i++) {
int j = fail[i];
while (j > 0 && p[i] != p[j]) j = fail[j];
if (p[i] == p[j]) j++;
fail[i + 1] = j;
}
// go[q][c]: dang khop q ky tu dau cua p, ghep them chu c thi khop bao nhieu
vector<array<int, 26>> go(m);
for (int q = 0; q < m; q++)
for (int c = 0; c < 26; c++) {
if (p[q] - 'a' == c) go[q][c] = q + 1;
else go[q][c] = (q == 0 ? 0 : go[fail[q]][c]);
}
vector<long long> dp(m, 0), nd(m); // dp[q]: so cach chon dang khop q ky tu
dp[0] = 1; // chua chon chu nao
for (int i = 0; i < n; i++) {
int c = s[i] - 'a';
nd = dp; // khong lay chu s[i]
for (int q = 0; q < m; q++) {
int t = go[q][c];
if (t < m) nd[t] = (nd[t] + dp[q]) % MOD; // lay chu s[i]
}
swap(dp, nd);
}
long long ans = 0;
for (int q = 0; q < m; q++) ans = (ans + dp[q]) % MOD;
cout << (ans - 1 + MOD) % MOD << "\n"; // bo cach chon rong
return 0;
}import sys
MOD = 1000000007
def main():
data = sys.stdin.buffer.read().split()
s = data[0]; p = data[1] # bytes
n = len(s); m = len(p)
# fail[i]: do dai bien dai nhat (vua la tien to vua la hau to) cua p[0..i-1]
fail = [0] * (m + 1)
for i in range(1, m):
j = fail[i]
while j > 0 and p[i] != p[j]:
j = fail[j]
if p[i] == p[j]:
j += 1
fail[i + 1] = j
# go[q][c]: dang khop q ky tu dau cua p, ghep them chu c thi khop bao nhieu
go = [[0] * 26 for _ in range(m)]
for q in range(m):
for c in range(26):
if p[q] - 97 == c:
go[q][c] = q + 1
else:
go[q][c] = 0 if q == 0 else go[fail[q]][c]
# voi moi chu c chi luu cac chuyen trang thai khac 0 (phan con lai ve 0)
nz = [[(q, go[q][c]) for q in range(m) if go[q][c] != 0] for c in range(26)]
dp = [0] * m # dp[q]: so cach chon dang khop q ky tu
dp[0] = 1 # chua chon chu nao
for ch in s:
nd = dp[:] # khong lay chu nay
z = sum(dp) # lay chu nay: mac dinh ve trang thai 0
for q, t in nz[ch - 97]:
z -= dp[q]
if t < m:
nd[t] += dp[q]
nd[0] += z
dp = [x % MOD for x in nd]
print((sum(dp) - 1) % MOD) # bo cach chon rong
main()Bộ test chấm "bắt" những lỗi nào?
Bộ test có 30 test: 10 test subtask 1 ($n \le 20$, có test $n = 1$ đáp án 0 và test $m > n$), 9 test subtask 2 ($n = 10^5$, $P$ không lặp chữ, có $P$ = 26 chữ cái), 11 test subtask 3 ($n = 10^5$, $P$ có chữ lặp với biên phức tạp: a…ab, abacaba…, aab…, xâu Fibonacci, ngẫu nhiên…, $m$ tới 100; $S$ được ghép từ các đoạn của $P$ để khớp một phần rất nhiều lần).
| Cách làm | Sub 1 (20%) | Sub 2 (30%) | Sub 3 (50%) | Điểm |
|---|---|---|---|---|
| Cách 1 – quay lui + cắt nhánh O(2n·m) | Đúng | TLE | TLE | 20 |
| Cách 2 – QHĐ khi P không có chữ lặp (còn lại quay lui) | Đúng | Đúng | TLE | 50 |
| Cách 3 – QHĐ + automaton KMP | Đúng | Đúng | Đúng | 100 |
| Sai 1 – luôn coi P không có chữ lặp | 9/10 test | Đúng | WA | 48 |
| Sai 2 – khi lệch chỉ lùi về fail[q] một lần | 9/10 test | Đúng | 2/11 test | ≈ 57,1 |
| Sai 3 – quên bỏ cách chọn rỗng | WA | WA | WA | 0 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test subtask 1 và quá 3 giây ở mọi test còn lại; Cách 2 đúng hết subtask 1, 2 và quá 3 giây ở mọi test subtask 3 (vì phải quay lui); Cách 3 đúng 30/30 test, mỗi test chưa tới 0,05 giây. Nếu không lập bảng go trước mà mỗi bước lại so khớp xâu để tìm trạng thái mới thì vẫn đúng nhưng mất khoảng 1 giây trên test lớn – rất dễ bị quá thời gian.
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 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét