Đếm Xâu Tốt
Đề bài
Cho hai xâu ký tự s1 và s2 có cùng độ dài $n$ và một xâu ký tự evil. Hãy đếm số lượng xâu "tốt" thỏa mãn đồng thời các điều kiện sau:
- Có độ dài bằng $n$.
- Có thứ tự từ điển lớn hơn hoặc bằng
s1. - Có thứ tự từ điển nhỏ hơn hoặc bằng
s2. - Không chứa xâu
evilnhư một xâu con (substring).
Vì kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của nó khi chia cho $10^9 + 7$.
Input
- Dòng đầu tiên chứa một số nguyên dương $n$ ($1 \le n \le 500$) là độ dài của các xâu
s1vàs2. - Dòng thứ hai chứa xâu ký tự
s1(chỉ gồm các chữ cái tiếng Anh in thường). - Dòng thứ ba chứa xâu ký tự
s2(chỉ gồm các chữ cái tiếng Anh in thường). - Dòng thứ tư chứa xâu ký tự
evil(chỉ gồm các chữ cái tiếng Anh in thường, độ dài không quá 50).
Dữ liệu đảm bảo s1 có thứ tự từ điển không lớn hơn s2 (tức là s1 $\le$ s2).
Output: một số nguyên duy nhất là kết quả của bài toán sau khi lấy modulo $10^9 + 7$.
Subtask
- 20% số test đầu tiên có độ dài các xâu s1, s2, evil $\le 10$.
- 80% số test còn lại không có giới hạn gì thêm.
| Input | Output | Giải thích |
|---|---|---|
2 aa da b | 51 | Có 25 xâu tốt bắt đầu bằng 'a': "aa", "ac", "ad", …, "az". Có 25 xâu tốt bắt đầu bằng 'c': "ca", "cc", "cd", …, "cz". Và 1 xâu tốt bắt đầu bằng 'd': "da". |
7 program progres pro | 0 | Tất cả các xâu nằm giữa "program" và "progres" đều bắt đầu bằng tiền tố "pro". Do đó, mọi xâu đều chứa "pro" là xâu con, không có xâu nào tốt. |
2 gx gz x | 2 | Các xâu độ dài 2 nằm giữa "gx" và "gz" là "gx", "gy", "gz". Xâu "gx" có chứa "x" nên chỉ có 2 xâu "gy" và "gz" là hợp lệ. |
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm và kèm lời giải để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 🥰.
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 OJBạ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é. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesTóm tắt đề bài: cho 2 chuỗi s1 và s2 có cùng độ dài. Đếm có bao nhiêu chuỗi có thứ tự từ điển $\ge$ s1, $\le$ s2 và không chứa chuỗi evil như một chuỗi con.
Phương pháp giải: quy hoạch động. Độ phức tạp $O(\text{len}(s) \cdot \text{len}(evil) \cdot 26 \cdot 4)$ với $\text{len}(s)$ là độ dài của 2 chuỗi.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Bước 1Bảng lastPos – ý tưởng của KMP
Bài này là một bài khá khó vì áp dụng quy hoạch động chữ số, đồng thời có sử dụng ý tưởng của thuật toán KMP, nên bạn đọc cần cân nhắc trước khi xem nha.
Ta cần đếm số chuỗi sao cho khi build các chuỗi này, không có chuỗi con nào giống toàn bộ chuỗi evil. Do đó ta cần một chiều trạng thái cho biết hiện tại phần cuối của chuỗi đang khớp được với tiền tố dài bao nhiêu của chuỗi evil.
Trước khi vào phần quy hoạch động, gọi lastPos[i][c] là độ dài tiền tố dài nhất của evil có thể khớp tiếp, nếu ta đang khớp được $i$ ký tự đầu của evil và thêm một ký tự $c$ vào sau. Ví dụ evil = "ababc": xét lastPos[4]['a'], tức là chuỗi đang xét là "abab" + 'a' = "ababa", khác với "ababc"; tuy nhiên 3 ký tự cuối "aba" trùng với tiền tố 3 ký tự đầu của evil, nên lastPos[4]['a'] = 3 (ô tô vàng). Ô tô đỏ là lúc khớp đủ cả chuỗi evil, trạng thái này bị cấm:
| i (đã khớp) | tiền tố | thêm 'a' | thêm 'b' | thêm 'c' | ký tự khác |
|---|---|---|---|---|---|
| 0 | (rỗng) | 1 | 0 | 0 | 0 |
| 1 | a | 1 | 2 | 0 | 0 |
| 2 | ab | 3 | 0 | 0 | 0 |
| 3 | aba | 1 | 4 | 0 | 0 |
| 4 | abab | 3 | 0 | 5 | 0 |
Cách build bảng: lấy chuỗi st là $i$ ký tự đầu tiên của evil, thêm ký tự $c$ vào sau. Duyệt độ dài $p$ từ $i + 1$ trở về 1, kiểm tra $p$ ký tự đầu tiên của evil có trùng với $p$ ký tự cuối cùng của chuỗi vừa tạo hay không, nếu có thì gán ngay lastPos[i][c] = p và dừng. Trong code, bảng này tên là pos[i][c], được tính trong hàm createLastPos (riêng trường hợp đang khớp 0 ký tự được xử lý thẳng trong vòng quy hoạch động: thêm đúng evil[0] thì khớp 1, không thì khớp 0).
100%Bước 2: quy hoạch động chữ số
Gọi f[i][j][state1][state2] là số lượng chuỗi có độ dài $i$, hiện tại đang khớp được tiền tố độ dài $j$ của chuỗi evil, và:
state1 = 0: chuỗi đã lớn hơn hẳns1(ở một vị trí nào đó trước đây);state1 = 1: chuỗi đang bằng đúng tiền tố củas1.state2 = 0: chuỗi đã nhỏ hơn hẳns2;state2 = 1: chuỗi đang bằng đúng tiền tố củas2.
Bài toán cơ sở: bắt đầu từ vị trí 0, f[0][0][1][1] = 1 (chuỗi rỗng, vẫn đang bằng cả tiền tố của s1 lẫn s2).
Chuyển trạng thái: từ f[i][j][state1][state2], thử gắn 1 ký tự $c$ vào vị trí thứ $i + 1$:
- nextj =
lastPos[j][c]. Nếunextjbằng độ dàievil, đồng nghĩa với việc toàn bộ chuỗievilxuất hiện trong chuỗi, ta bỏ qua trường hợp này. - nextstate1: nếu
state1 = 0, hoặcstate1 = 1và $c \gt$s1[i + 1]thìnextstate1 = 0; nếustate1 = 1và $c$ bằngs1[i + 1]thì vẫn là 1; nếustate1 = 1và $c \lt$s1[i + 1]thì chuỗi sẽ nhỏ hơns1, bỏ qua. - nextstate2: nếu
state2 = 0, hoặcstate2 = 1và $c \lt$s2[i + 1]thìnextstate2 = 0; bằng thì vẫn là 1; nếustate2 = 1và $c \gt$s2[i + 1]thì bỏ qua. - Cộng
f[i + 1][nextj][nextstate1][nextstate2]thêm một lượngf[i][j][state1][state2].
Kết quả: tổng các f[n][j][state1][state2] với state1, state2 từ 0 đến 1, và $j$ từ 0 đến len(evil) - 1 ($j$ không được phép bằng len(evil)).
Em nhập s1, s2, evil rồi bấm Tiếp để xem từng bước: mỗi bước thêm 1 ký tự, các xâu được gom theo trạng thái (đang khớp bao nhiêu ký tự của evil, còn bằng s1 / s2 hay đã thoát giới hạn) và mình chỉ đếm số lượng ở mỗi trạng thái chứ không liệt kê từng xâu:
state1, state2 chính là cờ "đang đi sát theo giới hạn" của quy hoạch động chữ số, chỉ khác là ở đây có cả giới hạn dưới (s1) lẫn giới hạn trên (s2) cùng lúc, nên cần 2 cờ thay vì 1.Source code để các bạn tham khảo nếu làm theo những gì mình phân tích ở trên:
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int dp[505][55][2][2];
int pos[55][26];
void createLastPos(const string &s){
int n = (int)s.size();
string st = "";
for(int i = 1; i < n; i++){
st += s[i - 1];
for(int c = 0; c <= 25; c++){
string tmp = st;
tmp += (char)(c + 'a');
for(int j = i + 1; j >= 1; j--){
if(c == s[j - 1] - 'a'){
int p = i + 1;
int q = j;
while(q > 0){
if(s[q - 1] != tmp[p - 1]){
break;
}
p--;
q--;
}
if(q == 0){
pos[i][c] = j;
break;
}
}
}
}
}
}
int findGoodStrings(int n, string s1, string s2, string evil){
memset(dp, 0, sizeof(dp));
memset(pos, 0, sizeof(pos));
int lenevil = (int)evil.size();
createLastPos(evil);
dp[0][0][1][1] = 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < lenevil; j++){
for(int state1 = 0; state1 <= 1; state1++){
for(int state2 = 0; state2 <= 1; state2++){
if(dp[i][j][state1][state2] == 0){
continue;
}
for(int nextChar = 0; nextChar <= 25; nextChar++){
if(j == lenevil - 1 && nextChar == evil[j] - 'a'){
continue;
}
if(state1 == 1 && nextChar < s1[i] - 'a'){
continue;
}
if(state2 == 1 && nextChar > s2[i] - 'a'){
continue;
}
int nextState1 = state1;
if(state1 == 1 && nextChar > s1[i] - 'a'){
nextState1 = 0;
}
int nextState2 = state2;
if(state2 == 1 && nextChar < s2[i] - 'a'){
nextState2 = 0;
}
int nextj = 0;
if(j == 0){
if(nextChar == evil[j] - 'a'){
nextj = 1;
}
}
else{
nextj = pos[j][nextChar];
}
if(nextj == lenevil){
continue;
}
(dp[i + 1][nextj][nextState1][nextState2] += dp[i][j][state1][state2]) %= mod;
}
}
}
}
}
int ans = 0;
for(int j = 0; j < lenevil; j++){
for(int state1 = 0; state1 <= 1; state1++){
for(int state2 = 0; state2 <= 1; state2++){
(ans += dp[n][j][state1][state2]) %= mod;
}
}
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
string s1, s2, evil;
cin >> n >> s1 >> s2 >> evil;
cout << findGoodStrings(n, s1, s2, evil);
return 0;
}import sys
mod = 1000000007
def createLastPos(s):
# pos[i][c]: độ dài tiền tố dài nhất của evil là hậu tố của (i ký tự đầu của evil + ký tự c)
n = len(s)
pos = [[0] * 26 for _ in range(n + 1)]
for i in range(1, n):
st = s[:i]
for c in range(26):
tmp = st + chr(c + 97)
for j in range(i + 1, 0, -1):
if tmp.endswith(s[:j]):
pos[i][c] = j
break
return pos
def findGoodStrings(n, s1, s2, evil):
lenevil = len(evil)
pos = createLastPos(evil)
ev = [ord(ch) - 97 for ch in evil]
# dp[j][state1][state2] cho độ dài hiện tại i (chỉ giữ 2 tầng i và i + 1)
dp = [[[0, 0], [0, 0]] for _ in range(lenevil)]
dp[0][1][1] = 1
for i in range(n):
lo = ord(s1[i]) - 97
hi = ord(s2[i]) - 97
ndp = [[[0, 0], [0, 0]] for _ in range(lenevil)]
for j in range(lenevil):
for state1 in range(2):
for state2 in range(2):
cur = dp[j][state1][state2]
if cur == 0:
continue
start = lo if state1 == 1 else 0
end = hi if state2 == 1 else 25
for nextChar in range(start, end + 1):
nextState1 = 1 if (state1 == 1 and nextChar == lo) else 0
nextState2 = 1 if (state2 == 1 and nextChar == hi) else 0
if j == 0:
nextj = 1 if nextChar == ev[0] else 0
else:
nextj = pos[j][nextChar]
if nextj == lenevil:
continue
cell = ndp[nextj][nextState1]
cell[nextState2] = (cell[nextState2] + cur) % mod
dp = ndp
ans = 0
for j in range(lenevil):
for state1 in range(2):
for state2 in range(2):
ans = (ans + dp[j][state1][state2]) % mod
return ans
data = sys.stdin.read().split()
n = int(data[0]); s1, s2, evil = data[1], data[2], data[3]
print(findGoodStrings(n, s1, s2, evil))Mình đã kiểm tra bản C++ và bản Python mình viết thêm với 140 bộ test ngẫu nhiên (độ dài tới 4, so với cách liệt kê mọi chuỗi), đều cho cùng kết quả. Với $n = 500$ và evil dài 50, bản C++ chạy khoảng 0.01 giây, bản Python khoảng 0.15 giây. Bản Python chỉ giữ 2 tầng $i$ và $i + 1$ của mảng f để tiết kiệm bộ nhớ, và với mỗi trạng thái chỉ thử các ký tự nằm trong khoảng cho phép thay vì thử cả 26 rồi bỏ qua.
Nhận xét
Đăng nhận xét