Nhảy lò cò ghép chữ (Đề tự luyện HSG Tin 12 – Bài 3) – QHĐ đếm dãy con có giới hạn bước nhảy và tổng tiền tố
Đề bài
Nhảy lò cò ghép chữ. Hàng $N$ ô trên sân trường, ô $i$ ghi chữ $s_i$; vạch xuất phát ở vị trí $0$, vạch đích ở vị trí $N + 1$. Với từ khoá $T$ dài $M$, một cách chơi là dãy ô $p_1 < p_2 < \ldots < p_M$ sao cho $s_{p_k} = T_k$ với mọi $k$, và nếu đặt $p_0 = 0$, $p_{M+1} = N + 1$ thì mọi bước nhảy $p_k - p_{k-1}$ ($k = 1..M+1$) đều không vượt quá $D$. Đếm số cách chơi, lấy dư cho $10^9 + 7$.
Dữ liệu vào: dòng đầu $N, M, D$ ($1 \le M \le 100$, $M \le N \le 10^5$, $1 \le D \le N + 1$); dòng 2 là $s$; dòng 3 là $T$ (chữ cái thường).
Kết quả: số cách chơi modulo $10^9 + 7$.
- Subtask 1 (20%): $N \le 20$.
- Subtask 2 (30%): $N \times D \le 10^6$.
- Subtask 3 (20%): $D = N + 1$.
- Subtask 4 (30%): không có ràng buộc gì thêm.
9 3 3
nssooxnon
son44 cách chơi (các ô đặt chân): $(2, 4, 7)$, $(2, 5, 7)$, $(3, 4, 7)$, $(3, 5, 7)$. Chẳng hạn $(2, 4, 9)$ cũng ghép được son nhưng bước từ ô 4 tới ô 9 dài $5 > 3$.
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 Nhảy lò cò ghép chữLời mở đầu
Bỏ lớp áo "lò cò" đi thì đây là bài đếm dãy con quen thuộc: đếm số cách chọn ra $M$ vị trí tăng dần trong $s$ sao cho các chữ ở đó ghép thành $T$. Bài gốc (không có $D$) là QHĐ kinh điển "đếm số lần xâu $T$ xuất hiện như một dãy con của $s$". Nút thắt ở đây là ràng buộc khoảng cách: hai ô đặt chân liên tiếp cách nhau không quá $D$, và cả bước đầu tiên (từ vạch xuất phát), bước cuối cùng (tới vạch đích) cũng vậy.
Ý tưởng QHĐ. Gọi $g[k][i]$ là số cách đặt chân lên $k$ ô đầu tiên của một cách chơi, sao cho ô thứ $k$ chính là ô $i$ (dĩ nhiên cần $s_i = T_k$). Ô đặt chân ngay trước đó (ô thứ $k - 1$, hoặc vạch xuất phát nếu $k = 1$) phải nằm trong cửa sổ $[i - D,\ i - 1]$:
Muốn đặt chân lên ô $i$ với chữ thứ $k$, bước trước phải xuất phát từ một ô trong cửa sổ $[i - D, i - 1]$ đã ghép xong $k - 1$ chữ.
Cách 1Quay lui – thử mọi cách nhảy · 20%
Mô phỏng đúng trò chơi: đang đứng ở vị trí pos và đã ghép được k chữ, thử mọi ô q trong tầm nhảy ($pos < q \le pos + D$) có chữ đúng bằng $T_{k+1}$ rồi nhảy tiếp. Khi đã ghép đủ $M$ chữ thì chỉ còn kiểm tra bước cuối: $N + 1 - pos \le D$.
#include <bits/stdc++.h>
using namespace std;
// Cach 1: quay lui - thu moi cach chon o dat chan tiep theo
const long long MOD = 1000000007LL;
int n, m, d;
string s, t;
long long cnt = 0;
void nhay(int pos, int k) { // dang dung o vi tri pos, da ghep duoc k chu
if (k == m) { // ghep du tu khoa: con buoc nhay toi vach dich
if (n + 1 - pos <= d) cnt++;
return;
}
for (int q = pos + 1; q <= n && q - pos <= d; q++)
if (s[q - 1] == t[k]) nhay(q, k + 1);
}
int main() {
cin >> n >> m >> d >> s >> t;
nhay(0, 0);
cout << cnt % MOD << '\n';
return 0;
}import sys
MOD = 1000000007
def main():
data = sys.stdin.read().split()
n, m, d = int(data[0]), int(data[1]), int(data[2])
s, t = data[3], data[4]
cnt = 0
# quay lui bang ngan xep (pos, k): dang dung o vi tri pos, da ghep duoc k chu
st = [(0, 0)]
while st:
pos, k = st.pop()
if k == m: # ghep du tu khoa: con buoc nhay toi vach dich
if n + 1 - pos <= d:
cnt += 1
continue
for q in range(pos + 1, min(n, pos + d) + 1):
if s[q - 1] == t[k]:
st.append((q, k + 1))
print(cnt % MOD)
main()Với $N \le 20$ thì có không quá $2^{20} \approx 10^6$ tập ô nên chạy rất nhanh. Bản Python mình viết bằng ngăn xếp thay cho đệ quy để khỏi lo giới hạn đệ quy. Còn $N$ lớn thì số cách nhảy bùng nổ (đáp án của nhiều test lớn hơn $10^9$ rất nhiều lần – đó là lý do đề bắt lấy dư).
Cách 2QHĐ, cộng trực tiếp cả cửa sổ – O(M·N·D) · 50%
Dùng mảng $g[k][i]$ như ở phần mở đầu, với $0 \le k \le M$, $0 \le i \le N$:
- Cơ sở: $g[0][0] = 1$ (đứng ở vạch xuất phát, chưa ghép chữ nào), $g[0][i] = 0$ với $i \ge 1$.
- Chuyển trạng thái: với $k \ge 1$, $i \ge 1$: nếu $s_i \ne T_k$ thì $g[k][i] = 0$; ngược lại $$g[k][i] = \sum_{j = \max(0,\, i - D)}^{i - 1} g[k - 1][j].$$
- Đáp án: ô cuối $p_M = i$ phải nhảy được tới vạch đích: $N + 1 - i \le D$, tức $i \ge N + 1 - D$: $$\text{đáp án} = \sum_{i = \max(1,\, N + 1 - D)}^{N} g[M][i].$$
Để ý cơ sở $g[0][0] = 1$ đã "lo" luôn cho bước nhảy đầu tiên: với $k = 1$, chỉ những ô $i \le D$ mới có $j = 0$ nằm trong cửa sổ.
#include <bits/stdc++.h>
using namespace std;
// Cach 2: QHD g[k][i], cong truc tiep cac o trong cua so [i - d, i - 1] - O(M * N * D)
const long long MOD = 1000000007LL;
int main() {
int n, m, d;
string s, t;
cin >> n >> m >> d >> s >> t;
vector<vector<long long>> g(m + 1, vector<long long>(n + 1, 0));
g[0][0] = 1; // vach xuat phat
for (int k = 1; k <= m; k++)
for (int i = 1; i <= n; i++) {
if (s[i - 1] != t[k - 1]) continue;
for (int j = max(0, i - d); j < i; j++) // o dat chan truoc do
g[k][i] = (g[k][i] + g[k - 1][j]) % MOD;
}
long long ans = 0;
for (int i = max(1, n + 1 - d); i <= n; i++) ans = (ans + g[m][i]) % MOD;
cout << ans << '\n';
return 0;
}import sys
MOD = 1000000007
def main():
data = sys.stdin.read().split()
n, m, d = int(data[0]), int(data[1]), int(data[2])
s, t = data[3], data[4]
g = [[0] * (n + 1) for _ in range(m + 1)]
g[0][0] = 1 # vach xuat phat
for k in range(1, m + 1):
prev, cur = g[k - 1], g[k]
for i in range(1, n + 1):
if s[i - 1] != t[k - 1]:
continue
tong = 0
for j in range(max(0, i - d), i): # o dat chan truoc do
tong += prev[j]
cur[i] = tong % MOD
ans = 0
for i in range(max(1, n + 1 - d), n + 1):
ans += g[m][i]
print(ans % MOD)
main()Subtask 2 có $N \cdot D \le 10^6$ nên tối đa $100 \cdot 10^6 = 10^8$ phép cộng – C++ chạy chưa tới nửa giây. Nhưng nếu $D$ lớn (chẳng hạn $D = N = 10^5$) thì lên tới $10^{12}$.
Cách 3D = N + 1: cửa sổ là cả đoạn đầu, cộng dồn – O(M·N) · 70%
Khi $D = N + 1$ thì mọi bước nhảy đều hợp lệ, cửa sổ $[\max(0, i - D), i - 1]$ chính là $[0, i - 1]$. Tổng $g[k-1][0] + \cdots + g[k-1][i-1]$ chỉ cần cộng dồn dần khi $i$ tăng: biến tong trước khi xét ô $i$ được cộng thêm $g[k-1][i-1]$. Đây chính là QHĐ "đếm số lần $T$ xuất hiện như dãy con của $s$" quen thuộc. Các subtask khác vẫn dùng Cách 2.
#include <bits/stdc++.h>
using namespace std;
// Cach 3: D = N + 1 (nhay xa tuy y) -> cong don chay O(N * M); con lai dung Cach 2
const long long MOD = 1000000007LL;
int main() {
int n, m, d;
string s, t;
cin >> n >> m >> d >> s >> t;
vector<vector<long long>> g(m + 1, vector<long long>(n + 1, 0));
g[0][0] = 1;
for (int k = 1; k <= m; k++) {
if (d == n + 1) {
long long tong = 0; // tong = g[k-1][0] + ... + g[k-1][i-1]
for (int i = 1; i <= n; i++) {
tong = (tong + g[k - 1][i - 1]) % MOD;
if (s[i - 1] == t[k - 1]) g[k][i] = tong;
}
} else {
for (int i = 1; i <= n; i++) {
if (s[i - 1] != t[k - 1]) continue;
for (int j = max(0, i - d); j < i; j++)
g[k][i] = (g[k][i] + g[k - 1][j]) % MOD;
}
}
}
long long ans = 0;
for (int i = max(1, n + 1 - d); i <= n; i++) ans = (ans + g[m][i]) % MOD;
cout << ans << '\n';
return 0;
}import sys
MOD = 1000000007
def main():
data = sys.stdin.read().split()
n, m, d = int(data[0]), int(data[1]), int(data[2])
s, t = data[3], data[4]
g = [[0] * (n + 1) for _ in range(m + 1)]
g[0][0] = 1
for k in range(1, m + 1):
prev, cur, c = g[k - 1], g[k], t[k - 1]
if d == n + 1:
tong = 0 # tong = g[k-1][0] + ... + g[k-1][i-1]
for i in range(1, n + 1):
tong = (tong + prev[i - 1]) % MOD
if s[i - 1] == c:
cur[i] = tong
else:
for i in range(1, n + 1):
if s[i - 1] != c:
continue
tong = 0
for j in range(max(0, i - d), i):
tong += prev[j]
cur[i] = tong % MOD
ans = 0
for i in range(max(1, n + 1 - d), n + 1):
ans += g[m][i]
print(ans % MOD)
main()Cách 4QHĐ + tổng tiền tố – O(M·N) · 100%
Cửa sổ trượt $[i - D, i - 1]$ là một đoạn liên tiếp của hàng $g[k - 1]$, nên tổng của nó lấy được trong $O(1)$ bằng tổng tiền tố. Với mỗi $k$, trước khi tính hàng $k$, ta lập
$$pre[x] = g[k-1][0] + g[k-1][1] + \cdots + g[k-1][x - 1] \quad (pre[0] = 0),$$khi đó $$g[k][i] = pre[i] - pre[\max(0, i - D)] \quad (\text{nếu } s_i = T_k).$$
Thêm hai chi tiết nhỏ:
- Trừ trong modulo: $pre$ đã được lấy dư nên $pre[i] - pre[lo]$ có thể âm; phải viết
(pre[i] - pre[lo] + MOD) % MOD. - Tiết kiệm bộ nhớ: hàng $k$ chỉ cần hàng $k - 1$, mà hàng $k - 1$ đã được "chép" hết vào $pre$, nên chỉ cần một mảng $g$ ghi đè lên chính nó (nhớ đặt $g[0] = 0$ sau hàng $k = 0$, vì vạch xuất phát chỉ dùng cho bước đầu tiên).
- Quên điều kiện bước cuối tới vạch đích (cộng cả $g[M][i]$ với $i < N + 1 - D$).
- Quên giới hạn bước đầu tiên (cho ô đầu tiên ở bất kỳ đâu).
- Nhầm "không quá $D$" thành "nhỏ hơn $D$": cửa sổ phải là $[i - D, i - 1]$ (đủ $D$ ô).
- Quên
+ MODkhi trừ hai tổng tiền tố.
Mô phỏng: bảng QHĐ và cửa sổ trượt
Em nhập hàng ô $s$, từ khoá $T$ và $D$ (tối đa 14 ô, từ khoá tối đa 5 chữ) rồi bấm Tiếp: mỗi bước tính một ô $g[k][i]$, các ô xanh nhạt là cửa sổ $[i - D, i - 1]$ ở hàng trên được cộng lại.
Code hoàn chỉnh:
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, d;
string s, t;
cin >> n >> m >> d >> s >> t;
vector<long long> g(n + 1, 0), pre(n + 2, 0);
g[0] = 1; // k = 0: dung o vach xuat phat
for (int k = 1; k <= m; k++) {
for (int i = 0; i <= n; i++) // pre[x] = g[0] + ... + g[x - 1]
pre[i + 1] = (pre[i] + g[i]) % MOD;
g[0] = 0;
for (int i = 1; i <= n; i++) {
if (s[i - 1] != t[k - 1]) { g[i] = 0; continue; }
int lo = max(0, i - d); // o dat chan truoc do: [i - d, i - 1]
g[i] = (pre[i] - pre[lo] + MOD) % MOD;
}
}
long long ans = 0;
for (int i = max(1, n + 1 - d); i <= n; i++) // buoc cuoi phai toi duoc vach dich
ans = (ans + g[i]) % MOD;
cout << ans << '\n';
return 0;
}import sys
from itertools import accumulate
MOD = 1000000007
def main():
data = sys.stdin.buffer.read().split()
n, m, d = int(data[0]), int(data[1]), int(data[2])
s = data[3].decode()
t = data[4].decode()
pos = {} # pos[c] = cac o ghi chu c
for i in range(1, n + 1):
pos.setdefault(s[i - 1], []).append(i)
g = [0] * (n + 1)
g[0] = 1 # k = 0: dung o vach xuat phat
for k in range(1, m + 1):
pre = list(accumulate(g, initial=0)) # pre[x] = g[0] + ... + g[x - 1]
g = [0] * (n + 1)
for i in pos.get(t[k - 1], ()):
lo = i - d if i > d else 0 # o dat chan truoc do: [i - d, i - 1]
g[i] = (pre[i] - pre[lo]) % MOD
lo = n + 1 - d if n + 1 - d > 1 else 1 # buoc cuoi phai toi duoc vach dich
print(sum(g[lo:n + 1]) % MOD)
main()itertools.accumulate (không lấy dư, số nguyên Python không tràn) và chỉ duyệt những ô có chữ đúng bằng $T_k$ (danh sách pos lập sẵn), nên đỡ được rất nhiều vòng lặp. Với PyPy 3 thì chạy thoải mái trong giới hạn.Bộ test chấm "bắt" những lỗi nào?
Bộ test có 39 test: 10 test subtask 1 ($N \le 20$: ví dụ, $N = 1$, $D = 1$ với $N = M$, test đáp án $0$ vì không tới được vạch đích, test chỉ bẫy bước đầu hoặc chỉ bẫy bước cuối...), 9 test subtask 2 ($N \cdot D \le 10^6$, $M = 50..100$, có test $(M + 1) D < N + 1$ nên đáp án bằng $0$), 9 test subtask 3 ($D = N + 1$, $N = 10^5$) và 11 test subtask 4 ($N = 10^5$, $M$ tới $100$, $D$ từ $991$ đến $N$; có test xâu toàn chữ z với $D = 991$ – vừa đủ nhảy tới đích). Hầu hết các test lớn có số cách vượt xa $10^9 + 7$.
| Cách làm | Sub 1 (20%) | Sub 2 (30%) | Sub 3 (20%) | Sub 4 (30%) | Điểm |
|---|---|---|---|---|---|
| Cách 1 – quay lui | Đúng | TLE | TLE | TLE | 20 |
| Cách 2 – QHĐ cộng cả cửa sổ $O(M N D)$ | Đúng | Đúng | TLE | TLE | 50 |
| Cách 3 – cộng dồn khi $D = N + 1$, còn lại Cách 2 | Đúng | Đúng | Đúng | TLE | 70 |
| Cách 4 – QHĐ + tổng tiền tố $O(M N)$ | Đúng | Đúng | Đúng | Đúng | 100 |
| Sai 1 – quên bước cuối tới vạch đích | 5/10 test | 2/9 test | Đúng | 2/11 test | ≈ 42 |
| Sai 2 – quên giới hạn bước đầu tiên | 5/10 test | 2/9 test | Đúng | 2/11 test | ≈ 42 |
| Sai 3 – bước nhảy < D (cửa sổ thiếu một ô) | 2/10 test | 3/9 test | Đúng | 2/11 test | ≈ 40 |
Sai 4 – quên + MOD khi trừ tổng tiền tố | Đúng | 4/9 test | Đúng | 6/11 test | ≈ 70 |
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à chạy quá 3 giây ở mọi test còn lại; Cách 2 đúng hết hai subtask đầu (test lâu nhất 0,36 giây) và quá giờ ở mọi test có $D$ lớn; Cách 3 đúng thêm cả 9 test $D = N + 1$ nhưng vẫn quá giờ ở 11 test subtask 4; Cách 4 đúng 39/39 test, test lâu nhất khoảng 0,17 giây. Để ý cả bốn lỗi sai đều "qua" subtask 3: khi $D = N + 1$ thì không còn ràng buộc khoảng cách nào, cửa sổ luôn bắt đầu từ $0$ nên cũng không có phép trừ ra số âm. Ví dụ của đề cũng cố ý để lỗi quên bước đầu, quên bước cuối và quên + MOD đều vẫn ra đúng $4$.
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