Nguồn: HSG 12 năm 2018–2019 (LQDOJ)Độ khó: Trung bìnhXâu ký tựĐếm – tổ hợp
Đề bài
Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự $0$ hoặc $1$.
Xâu $v$ gọi là xâu con của $w$ nếu xâu $v$ có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu $w$.
Ví dụ: xâu 010 có các xâu con là: 0, 1, 0, 01, 10, 010.
Yêu cầu: Cho trước một giá trị $k$, hãy đếm xem có bao nhiêu xâu con chứa đúng $k$ ký tự $1$.
Input:
Dòng 1: chứa một số nguyên $k$ $(0 \le k \le 10^6)$.
Dòng 2: chứa một xâu nhị phân có độ dài $\le 10^6$.
Output:
Ghi ra một số nguyên duy nhất là kết quả tìm được.
Scoring: $len(s)$ là độ dài xâu nhị phân.
Subtask 1 (40% số điểm): $1 \le k \le len(s) \le 500$.
Subtask 2 (30% số điểm): $1000 \le k \le len(s) \le 10000$.
Subtask 3 (30% số điểm): $10^5 \le k \le len(s) \le 10^6$.
Ví dụ – input
2
01010
Ví dụ – output
4
Giải thích: có 4 xâu con chứa 2 ký tự 1 là: 101, 0101, 1010, 01010.
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, kèm theo đó là nội dung mình đã hướng dẫn em ấy để bạn nào không giải quyết được thì có thể tham khảo nhen. Bài này bạn có thể nộp tại đây nha:
Dành cho tất cả mọi ngườiNộp bài trên LQDOJ
Link này công khai, 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é. 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.
Ok anh sẽ cho em 1 gợi ý nhìn ra hướng xử lý của nó nha, hãy nhìn test này:
Ví dụ – input
2
010011001001
Ví dụ – output
17
Bài này nếu làm theo cách brute force (vét cạn) thì quá đơn giản: tại mỗi vị trí index $i$, xét tất cả các index $j \ge i$, đoạn con từ $i$ đến $j$ nào có đúng $k$ ký tự 1 thì tính. Ví dụ ta có chuỗi abcd thì sẽ có các xâu con:
aababcabcdbbcbcdccdd
Chuỗi dài $N$ có $\frac{N(N+1)}{2}$ xâu con – với $N = 4$ là 10 xâu con.
Mẹo nhỏ: khi cố định $i$ và cho $j$ chạy sang phải, ta đếm dồn số ký tự 1 trong biến cnt; một khi cnt > k thì kéo dài thêm cũng chỉ tăng chứ không giảm, nên break luôn. Code vét cạn mình viết thêm để các bạn tham khảo (và dùng để kiểm tra code tối ưu):
Code vét cạn O(N²) – chỉ qua Subtask 1
#include <bits/stdc++.h>
using namespace std;
int main(){
int k;
string s;
cin >> k >> s;
int n = s.length();
long long res = 0;
for(int i = 0; i < n; ++i){
int cnt = 0;
for(int j = i; j < n; ++j){
if(s[j] == '1') cnt++;
if(cnt > k) break;
if(cnt == k) res++;
}
}
cout << res;
return 0;
}
k = int(input())
s = input().strip()
n = len(s)
res = 0
for i in range(n):
cnt = 0
for j in range(i, n):
if s[j] == '1':
cnt += 1
if cnt > k:
break
if cnt == k:
res += 1
print(res)
C++▶ Chạy tay từng dòng codeCách 1: vét cạn mọi xâu con s[i..j], đếm dồn số ký tự 1, O(N²).
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4int main(){
5int k;
6string s;
7cin >> k >> s;
8int n = s.length();
9longlong res = 0;
10for(int i = 0; i < n; ++i){
11int cnt = 0;
12for(int j = i; j < n; ++j){
13if(s[j] == '1') cnt++;
14if(cnt > k) break;
15if(cnt == k) res++;
16 }
17 }
18cout << res;
19return0;
20}
Không gian$O(N)$ (lưu xâu)
Thời gian$O(N^2)$ – chỉ qua Subtask 1
Nhưng nếu làm vậy trước mắt là thấy độ phức tạp sẽ là $O(N^2)$ với $N$ là độ dài chuỗi, mà đề cho chuỗi độ dài tối đa $10^6$, thì $(10^6)^2 = 10^{12}$, đã vượt quá $10^8$ phép tính trong giới hạn 1 giây rồi nên sẽ bị TLE. Cách này chỉ qua được Subtask 1 (và may mắn thì Subtask 2), vì thế phải tìm ra một cách tốt hơn.
Ý tưởngNhìn vào vị trí các ký tự 1
Bài này có thể giải quyết trong $O(N)$ là cách tối ưu nhất nhé, sẽ làm được nếu em nhìn ra quy luật sau. Hãy nhìn lại test $k = 2$, $s$ = 010011001001: nghĩa là cần đếm xem có bao nhiêu xâu con liên tiếp có đúng 2 ký tự 1.
Đầu tiên ta hãy thử liệt kê ra tất cả các vị trí index (tính từ 0) của các ký tự 1 trong chuỗi, ta sẽ có mảng $a = [1, 4, 5, 8, 11]$. Bây giờ với $k = 2$ thì ta cứ xét từng cặp $k$ vị trí liên tiếp trong mảng này: start là số 1 đầu tiên, finish là số 1 cuối cùng của nhóm.
s = 010011001001 (số nhỏ phía trên là index)
00112030415160708190100111
Mảng vị trí các số 1: a = [1, 4, 5, 8, 11] · các cặp (k = 2): (1, 4), (4, 5), (5, 8), (8, 11)
Cặp 1: start = 1, finish = 4
2 phần tử đầu mảng $a$ là $1, 4$, nghĩa là từ index 1 đến index 4 trong chuỗi ban đầu chứa đúng 2 ký tự 1, em coi đúng không?
Bên trái: trước start không có số 1 nào (đây là cặp đầu tiên), nên điểm bắt đầu của xâu con có thể chọn từ index 0 đến index start = 1 → có 2 cách.
Bên phải: số 1 tiếp theo sau finish = 4 ở index 5, nên điểm kết thúc tối đa chỉ đến 5 − 1 = 4 chứ không đến 5 được, vì nếu không sẽ thành xâu con có 3 ký tự 1 → từ 4 đến 4 có 1 cách.
Tổng cộng ta có $2 \cdot 1 = 2$ xâu con: 01001 và 1001.
Cặp 2: start = 4, finish = 5
Trước start, số 1 gần nhất ở index 1, nên điểm bắt đầu lấy từ sau vị trí đó đến start: từ index 2 đến 4 → 3 cách.
Sau finish, số 1 tiếp theo ở index 8, nên điểm kết thúc từ 5 đến 7 → 3 cách.
Số 1 trước start ở index 5 → điểm bắt đầu từ 6 đến 8 → 3 cách.
Sau finish = 11 không còn số 1 nào nữa vì đây là số 1 cuối cùng, nên điểm kết thúc tối đa là index cuối của chuỗi. Chuỗi dài 12 nên index cuối là 11 → từ 11 đến 11 có 1 cách.
Vậy tổng kết lại, số xâu con liên tiếp có đúng $k = 2$ ký tự 1 là $2 + 9 + 3 + 3 = \boxed{17}$. Đó là cách để chỉ cần 1 lần duyệt O(N) qua chuỗi là xử lý được nha em 😃
Công thức gọn
Với nhóm $k$ số 1 liên tiếp từ $a[start]$ đến $a[finish]$ (với $finish = start + k - 1$), đặt $x$ = vị trí số 1 ngay trước ($x = -1$ nếu không có) và $y$ = vị trí số 1 ngay sau ($y = len(s)$ nếu không có). Số xâu con nhận đúng nhóm này là $(a[start] - x) \cdot (y - a[finish])$. Cộng lại cho mọi nhóm là xong.
Trường hợp đặc biệt k = 0
Tất nhiên còn 1 số trường hợp đặc biệt, ví dụ khi $k = 0$ phải xét riêng ^^. Lúc này xâu con hợp lệ là xâu con chỉ gồm toàn ký tự 0. Các số 1 cắt chuỗi thành từng đoạn 0 liên tiếp; một đoạn gồm $cnt$ số 0 có $\frac{cnt \cdot (cnt + 1)}{2}$ xâu con (chọn 2 đầu mút trong đoạn). Cộng lại tất cả các đoạn (kể cả đoạn trước số 1 đầu tiên và đoạn sau số 1 cuối cùng). Nếu chuỗi không có số 1 nào thì cả chuỗi là 1 đoạn, đáp án là $\frac{len \cdot (len + 1)}{2}$. Ngoài ra nếu $k$ lớn hơn số lượng ký tự 1 thì đáp án là 0.
Minh hoạĐếm theo từng nhóm k số 1
Em nhập $k$ và xâu $s$ (tối đa 30 ký tự) rồi bấm Tiếp để xem từng nhóm: vùng chọn điểm đầu (xanh dương), nhóm $k$ số 1 (vàng), vùng chọn điểm cuối (xanh lá):
Ví dụ nhanh:
Cách 2Code O(N) theo vị trí các số 1
Source code giải quyết theo tư tưởng anh đã trình bày ở trên và cũng đã nộp thành công trên web, em xem để được hiểu rõ hơn. Anh nói trước là code này anh code vội ra theo đúng tư tưởng đã chia sẻ đó với em chứ chưa có clean đâu nha, anh sợ clean lại mất công em đọc không hiểu. Em xem hiểu rồi clean lại sau nhé:
#include <bits/stdc++.h>
using namespace std;
long long solve(const string &s, int k){
vector<int> a;
for(int i = 0; i < s.length(); ++i){
if(s[i] == '1'){
a.push_back(i);
}
}
if(k > a.size()){
return 0;
}
if(k == 0){
if(a.size() == 0){
long long l = s.length();
return (l * (l + 1)) / 2;
}
else{
long long res = 0, cnt = 0;
int start = 0;
for(int i = 0; i < a.size(); ++i){
if(start <= a[i] - 1){
cnt = a[i] - start;
res += (cnt * (cnt + 1)) / 2;
}
start = a[i] + 1;
}
if(s.back() != '1'){
cnt = s.length() - (a.back() + 1);
res += (cnt * (cnt + 1)) / 2;
}
return res;
}
}
long long res = 0;
int start = 0, finish = k - 1;
while(finish < a.size()){
int x, y;
if(start == 0){
x = -1;
}
else{
x = a[start - 1];
}
if(finish == a.size() - 1){
y = s.length();
}
else{
y = a[finish + 1];
}
long long s1 = a[start] - x;
long long s2 = y - a[finish];
res += s1 * s2;
start++;
finish++;
}
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int k;
string s;
cin >> k >> s;
cout << solve(s, k);
return 0;
}
def solve(s: str, k: int) -> int:
a = [i for i, ch in enumerate(s) if ch == '1']
if k > len(a):
return 0
if k == 0:
if len(a) == 0:
l = len(s)
return (l * (l + 1)) // 2
else:
res = 0
start = 0
for idx in a:
if start <= idx - 1:
cnt = idx - start
res += (cnt * (cnt + 1)) // 2
start = idx + 1
if s[-1] != '1':
cnt = len(s) - (a[-1] + 1)
res += (cnt * (cnt + 1)) // 2
return res
res = 0
start = 0
finish = k - 1
while finish < len(a):
if start == 0:
x = -1
else:
x = a[start - 1]
if finish == len(a) - 1:
y = len(s)
else:
y = a[finish + 1]
s1 = a[start] - x
s2 = y - a[finish]
res += s1 * s2
start += 1
finish += 1
return res
k = int(input())
s = input()
print(solve(s, k))
C++▶ Chạy tay từng dòng codeCách 2: gom vị trí các số 1 vào a, mỗi nhóm k số 1 liên tiếp đóng góp s1 × s2 xâu con, O(N).
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4longlong solve(conststring &s, int k){
5vector<int> a;
6for(int i = 0; i < s.length(); ++i){
7if(s[i] == '1'){
8 a.push_back(i);
9 }
10 }
11if(k > a.size()){
12return0;
13 }
14if(k == 0){
15if(a.size() == 0){
16longlong l = s.length();
17return (l * (l + 1)) / 2;
18 }
19else{
20longlong res = 0, cnt = 0;
21int start = 0;
22for(int i = 0; i < a.size(); ++i){
23if(start <= a[i] - 1){
24 cnt = a[i] - start;
25 res += (cnt * (cnt + 1)) / 2;
26 }
27 start = a[i] + 1;
28 }
29if(s.back() != '1'){
30 cnt = s.length() - (a.back() + 1);
31 res += (cnt * (cnt + 1)) / 2;
32 }
33return res;
34 }
35 }
36longlong res = 0;
37int start = 0, finish = k - 1;
38while(finish < a.size()){
39int x, y;
40if(start == 0){
41 x = -1;
42 }
43else{
44 x = a[start - 1];
45 }
46if(finish == a.size() - 1){
47 y = s.length();
48 }
49else{
50 y = a[finish + 1];
51 }
52longlong s1 = a[start] - x;
53longlong s2 = y - a[finish];
54 res += s1 * s2;
55 start++;
56 finish++;
57 }
58return res;
59}
60
61int main(){
62ios::sync_with_stdio(0);
63cin.tie(0);
64int k;
65string s;
66cin >> k >> s;
67cout << solve(s, k);
68return0;
69}
Đánh giá độ phức tạp của cách làm này:
Không gian$O(N)$ cho xâu và mảng vị trí $a$
Thời gian$O(N)$: 1 lần duyệt lấy vị trí số 1 + 1 lần duyệt các nhóm
Lưu ý kết quả có thể rất lớn: chuỗi $10^6$ ký tự 0 với $k = 0$ cho đáp án $500\,000\,500\,000$, vượt kiểu int, nên res, s1, s2 phải là long long.
Ghi chú của mình: code C++ và Python của Cách 2 là của anh, code vét cạn Cách 1 mình viết thêm. Tất cả đã được kiểm tra với 250 bộ test ngẫu nhiên (xâu dài đến 25 ký tự, có cả $k = 0$, $k$ lớn hơn số ký tự 1, xâu toàn 0 hoặc toàn 1), so với cách đếm trực tiếp mọi xâu con – khớp hết. Với xâu dài $10^6$, bản C++ của Cách 2 chạy khoảng 0.03 giây, bản Python khoảng 0.3 giây; còn vét cạn chạy hơn 10 giây.
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 😇
Nguồn: CSES 1746 – Array DescriptionĐộ khó: Trung bìnhQuy hoạch độngĐệ quy có nhớ
Đề bài
Bạn biết rằng một mảng có $n$ số nguyên giữa $1$ và $m$ và chênh lệch tuyệt đối giữa hai giá trị liền kề nhiều nhất là $1$.
Cho một mô tả về mảng mà trong đó một số giá trị có thể không xác định, nhiệm vụ của bạn là đếm số lượng mảng khớp với mô tả.
Input
Dòng đầu vào đầu tiên có hai số nguyên $n$ và $m$: kích thước mảng và giới hạn trên cho mỗi giá trị.
Dòng tiếp theo có $n$ số nguyên $x_1, x_2, \dots, x_n$: nội dung của mảng. Giá trị $0$ biểu thị một giá trị không xác định.
Output
In một số nguyên: số lượng dãy chia lấy dư cho $10^9 + 7$.
Constraints
$1 \le n \le 10^5$
$1 \le m \le 100$
$0 \le x_i \le m$
Ví dụ – input
3 5
2 0 2
Ví dụ – output
3
Note: các dãy $[2, 1, 2]$, $[2, 2, 2]$, $[2, 3, 2]$ khớp với mô tả.
Lời mở đầu
Thêm một bài quy hoạch động đếm rất hay trong bộ CSES. Cũng như mọi khi, mình đi từ vét cạn, cải tiến lên đệ quy có nhớ (top-down), rồi công thức truy hồi (bottom-up), cuối cùng rút gọn bộ nhớ còn mảng 1 chiều. Hy vọng mang đến được giá trị cho các bạn 😇.
Dành cho tất cả mọi ngườiNộp bài trên LQDOJ
Link này công khai, 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é. 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.
Trước tiên mình sẽ tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu như sau:
Đề bài nói gì?
Cho bạn một mảng gồm $n$ số nguyên $a[1], a[2], \dots, a[n]$ $(1 \le n \le 10^5)$ và số $m$ $(1 \le m \le 100)$, $0 \le a[i] \le m$. Có những giá trị trong mảng ở dạng không xác định ($a[i] = 0$), những phần tử đó ta có thể thay bằng số bất kỳ từ $1$ tới $m$. Hãy đếm số lượng mảng tạo ra được sao cho chênh lệch tuyệt đối giữa hai giá trị liền kề nhiều nhất là 1. In ra số lượng đó chia lấy dư cho $10^9 + 7$.
Ví dụ: $n = 3$, $m = 5$, $a = \{2, 0, 2\}$. Output: $3$. Ta có thể tạo ra các mảng $\{2, 1, 2\}$, $\{2, 2, 2\}$, $\{2, 3, 2\}$.
Cách 1Vét cạn đệ quy
Cách làm đơn giản nhất của bài này chính là vét cạn, tức là thử mọi trường hợp có thể. Phần tử nào trong mảng mà $= 0$ thì ta thay thử lần lượt các giá trị từ $1$ tới $m$ vào, sau đó duyệt qua mảng để kiểm tra chênh lệch giữa hai giá trị liền kề có vượt quá $1$ không. Cách này thì chắc chắn bị TLE rồi, và cũng khó để cải tiến lên nữa: giả sử toàn bộ các phần tử đều $= 0$, mỗi phần tử thử $m$ trường hợp, suy ra có tổng cộng $m^n$ trường hợp. Với $m = 100$, $n = 10^5$ thì có $10^{2 \cdot 10^5}$ trường hợp, không thể thử hết trong 1 giây được. Vậy ta đến với cách vét cạn cải tiến hơn nha.
Ta sẽ thấy rằng nếu phần tử thứ $n$ của ta là $x$ thì phần tử thứ $n - 1$ chỉ có thể là $x - 1$ hoặc $x$ hoặc $x + 1$ mà thôi, vì độ chênh lệch giữa các phần tử liên tiếp không được vượt quá $1$ mà.
Từ ý tưởng đó ta xây dựng hàm đệ quy như sau:
Hàm Try(n, m, x) trả về số lượng dãy có chiều dài $n$, thoả mãn điều kiện chênh lệch giữa các phần tử liên tiếp không vượt quá $1$, các phần tử nằm trong khoảng từ $1$ tới $m$, khớp với mô tả, và phần tử thứ $n$ bằng $x$ ($a[n] = x$).
Điều kiện dừng. Ta đang xét phần tử thứ $n$ và $a[n]$ sẽ $= x$. Ta có:
1/ Nếu $x$ không nằm trong khoảng từ $1$ tới $m$ thì đó là dãy không hợp lệ, trả về $0$. Tức là khi $x < 1$ hoặc $x > m$:
C++
if(x < 1 || x > m) {
return 0;
}
Python
if x < 1 or x > m:
return 0
2/ Nếu $a[n]$ là một giá trị xác định ($a[n] \ne 0$) mà $a[n]$ còn khác $x$ thì cũng không có dãy nào hợp lệ, vì ta cần dãy có phần tử thứ $n$ bằng $x$ mà $a[n]$ lại $\ne x$. Còn nếu $a[n] = 0$ thì đây là giá trị không xác định, ta hoàn toàn có thể gán $a[n] = x$ nha. Nên phải kiểm tra $a[n] \ne 0$ rồi mới kiểm tra $a[n] \ne x$:
C++
if(a[n] && a[n] != x) {
return 0;
}
Python
if a[n] and a[n] != x:
return 0
3/ Đến đây ta chắc chắn ($a[n] = 0$ hoặc $a[n] = x$) và $1 \le x \le m$. Lúc này nếu $n = 1$, tức dãy chỉ có chiều dài $1$, thì với phần tử thứ $n = x$ ta có đúng một dãy, trả về $1$:
C++
if(n == 1) {
return 1;
}
Python
if n == 1:
return 1
Xử lý chạy. Số lượng dãy chiều dài $n$ với $a[n] = x$ $=$ (số dãy chiều dài $n - 1$ với $a[n - 1] = x - 1$) $+$ (số dãy chiều dài $n - 1$ với $a[n - 1] = x$) $+$ (số dãy chiều dài $n - 1$ với $a[n - 1] = x + 1$). Viết lại:
Công thức
$$Try(n, m, x) = \big(Try(n - 1, m, x - 1) + Try(n - 1, m, x) + Try(n - 1, m, x + 1)\big) \bmod (10^9 + 7)$$
Và vì cần lấy phần dư cho $10^9 + 7$ nên hãy nhớ chia dư lúc trả về. Kết quả của bài chia làm 2 trường hợp:
TH1: $a[n] \ne 0$ (xác định) thì kết quả chính là số dãy chiều dài $n$ có phần tử cuối $= a[n]$, tức Try(n, m, a[n]).
TH2: $a[n] = 0$ (không xác định) thì phần tử cuối có thể là $1, 2, \dots, m$, kết quả $=$ Try(n, m, 1) + Try(n, m, 2) + … + Try(n, m, m). Ta lưu vào biến res và sau mỗi lần cộng phải chia dư luôn, vì theo đồng dư thức $(a + b) \bmod m$ $= \big((a \bmod m) + (b \bmod m)\big) \bmod m$.
Sau đây là source code của mình về ý tưởng trên cho bạn nào cần tham khảo nha:
Code vét cạn đệ quy – 17/27 test
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (ll)1e9 + 7;
const int N = (int)1e5 + 5;
int a[N];
ll Try(int n, int m, int x) {
if(x < 1 || x > m) {
return 0;
}
if(a[n] && a[n] != x) {
return 0;
}
if(n == 1) {
return 1;
}
return (Try(n - 1, m, x - 1) + Try(n - 1, m, x) + Try(n - 1, m, x + 1)) % mod;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
ll res = 0;
if(a[n]) {
res = Try(n, m, a[n]);
}
else {
for(int i = 1; i <= m; ++i) {
res += Try(n, m, i);
res %= mod;
}
}
cout << res;
return 0;
}
import sys
sys.setrecursionlimit(10**5)
MOD = 10**9 + 7
N = 10**5 + 5
a = [0] * N
def Try(n, m, x):
if x < 1 or x > m:
return 0
if a[n] and a[n] != x:
return 0
if n == 1:
return 1
return (Try(n - 1, m, x - 1) + Try(n - 1, m, x) + Try(n - 1, m, x + 1)) % MOD
# main
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
for i in range(1, n + 1):
a[i] = arr[i - 1]
res = 0
if a[n]:
res = Try(n, m, a[n])
else:
for i in range(1, m + 1):
res += Try(n, m, i)
res %= MOD
print(res)
C++▶ Chạy tay từng dòng codeCách 1: đệ quy Try(n, m, x), phần tử trước chỉ có thể là x − 1, x, x + 1.
Dữ liệu mẫu:
1#include<bits/stdc++.h>
2#defineendl'\n'
3usingnamespace std;
4typedeflonglongll;
5constll mod = (ll)1e9 + 7;
6constint N = (int)1e5 + 5;
7int a[N];
8ll Try(int n, int m, int x) {
9if(x < 1 || x > m) {
10return0;
11 }
12if(a[n] && a[n] != x) {
13return0;
14 }
15if(n == 1) {
16return1;
17 }
18return (Try(n - 1, m, x - 1) + Try(n - 1, m, x) + Try(n - 1, m, x + 1)) % mod;
19}
20int main() {
21ios::sync_with_stdio(0);
22cin.tie(0);
23int n, m;
24cin >> n >> m;
25for(int i = 1; i <= n; ++i) {
26cin >> a[i];
27 }
28ll res = 0;
29if(a[n]) {
30 res = Try(n, m, a[n]);
31 }
32else {
33for(int i = 1; i <= m; ++i) {
34 res += Try(n, m, i);
35 res %= mod;
36 }
37 }
38cout << res;
39return0;
40}
Giải thích một số chỗ trong code
ios::sync_with_stdio(0); cin.tie(0); 2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên kinh nghiệm trong các bài mà cần nhập xuất nhiều thì ta nên sử dụng 2 dòng này. Trong bài này đầu vào có thể lên tới $10^5$ số nên các bạn nên thêm 2 dòng này vào nha. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.
Không gian$O(n)$ (độ sâu đệ quy)
Thời gian$O(3^n)$ – hàm mũ
Với cách trên chắc chắn ta sẽ bị TLE, cụ thể ta ăn được 17 trên 27 test nha. Tuy nhiên hãy vẫn nên cài đặt nó để sau này lấy nó làm công cụ kiểm tra tính chính xác cho cách làm tối ưu, hoặc biết đâu ta có thể cải tiến nó thành quy hoạch động top-down.
Cách 2Quy hoạch động top-down (đệ quy có nhớ)
Lý do code trên chạy lâu chính là vì nếu ta đã tính 1 vấn đề rồi mà lần sau gặp lại thì vẫn phải đi tính lại nó, việc tính đi tính lại này tốn rất nhiều thời gian. Tư tưởng của thuật toán là dùng 1 kiểu dữ liệu (mảng, vector, map…) để lưu trữ những kết quả đã tính, gặp lại thì chỉ việc trả về kết quả mà thôi. Ta làm như sau:
Tham số nào thay đổi? Hàm Try() có 3 tham số $n, m, x$, chỉ có $n$ và $x$ thay đổi ở mỗi lần gọi đệ quy, còn $m$ thì không. Vậy ta tạo mảng 2 chiều F, phần tử F[n][x] lưu kết quả của Try(n, m, x).
Giới hạn tham số? $n$ tối đa $10^5$, $x$ tối đa $m = 100$. Vậy ta tạo mảng F[10^5 + 5][100 + 5], mình thường cộng thêm 5 để thừa ra vài phần tử, tránh truy cập ra ngoài phạm vi mảng.
Giá trị hàm không thể trả về? Hàm Try() nhỏ nhất trả về $0$, vậy $-1$ là giá trị không thể trả về. Ta lấp đầy F = -1; sau mục điều kiện dừng, nếu F[n][x] != -1 nghĩa là đã tính rồi, chỉ việc trả về F[n][x]. Ngược lại thì đi tính như phần xử lý chạy, gán kết quả vào F[n][x] rồi trả về.
Code quy hoạch động top-down – AC
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (ll)1e9 + 7;
const int N = (int)1e5 + 5;
int a[N];
ll f[N][105];
ll Try(int n, int m, int x) {
if(x < 1 || x > m) {
return 0;
}
if(a[n] && x != a[n]) {
return 0;
}
if(n == 1) {
return 1;
}
if(f[n][x] != -1) {
return f[n][x];
}
return f[n][x] = (Try(n - 1, m, x - 1) + Try(n - 1, m, x) + Try(n - 1, m, x + 1)) % mod;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
fill(&f[0][0], &f[n][m + 1], -1);
ll res = 0;
if(a[n]) {
res = Try(n, m, a[n]);
}
else {
for(int i = 1; i <= m; ++i) {
res += Try(n, m, i);
res %= mod;
}
}
cout << res;
return 0;
}
import sys
sys.setrecursionlimit(10**5)
MOD = 10**9 + 7
N = 10**5 + 5
a = [0] * N
f = None
def Try(n, m, x):
if x < 1 or x > m:
return 0
if a[n] and x != a[n]:
return 0
if n == 1:
return 1
if f[n][x] != -1:
return f[n][x]
f[n][x] = (Try(n - 1, m, x - 1) + Try(n - 1, m, x) + Try(n - 1, m, x + 1)) % MOD
return f[n][x]
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
for i in range(1, n + 1):
a[i] = arr[i - 1]
f = [[-1] * (m + 2) for _ in range(n + 1)]
res = 0
if a[n]:
res = Try(n, m, a[n])
else:
for i in range(1, m + 1):
res += Try(n, m, i)
res %= MOD
print(res)
C++▶ Chạy tay từng dòng codeCách 2: đệ quy có nhớ, lưu f[n][x] để không tính lại.
Dữ liệu mẫu:
1#include<bits/stdc++.h>
2#defineendl'\n'
3usingnamespace std;
4typedeflonglongll;
5constll mod = (ll)1e9 + 7;
6constint N = (int)1e5 + 5;
7int a[N];
8ll f[N][105];
9ll Try(int n, int m, int x) {
10if(x < 1 || x > m) {
11return0;
12 }
13if(a[n] && x != a[n]) {
14return0;
15 }
16if(n == 1) {
17return1;
18 }
19if(f[n][x] != -1) {
20return f[n][x];
21 }
22return f[n][x] = (Try(n - 1, m, x - 1) + Try(n - 1, m, x) + Try(n - 1, m, x + 1)) % mod;
23}
24int main() {
25ios::sync_with_stdio(0);
26cin.tie(0);
27int n, m;
28cin >> n >> m;
29for(int i = 1; i <= n; ++i) {
30cin >> a[i];
31 }
32fill(&f[0][0], &f[n][m + 1], -1);
33ll res = 0;
34if(a[n]) {
35 res = Try(n, m, a[n]);
36 }
37else {
38for(int i = 1; i <= m; ++i) {
39 res += Try(n, m, i);
40 res %= mod;
41 }
42 }
43cout << res;
44return0;
45}
Giải thích một số chỗ trong code
return f[n][x] = (Try(…) + Try(…) + Try(…)) % mod; ở đây chính là ta gán f[n][x] = … rồi sau đó return f[n][x].
fill(&f[0][0], &f[n][m + 1], -1); đây chính là bước lấp đầy mảng F bằng $-1$. Bạn nào không biết hàm fill thì dùng vòng for vẫn được nha, độ phức tạp như nhau.
Không gian$O(n \cdot m)$
Thời gian$O(n \cdot m)$
Không gian thật ra là $O(n \cdot m + n)$ vì dùng mảng f và mảng a, nhưng theo quy tắc BigO thì là $O(n \cdot m)$. Thời gian: trường hợp xấu nhất hàm Try() phải lấp đầy toàn bộ mảng F, thay $n = 10^5$, $m = 100$ cần khoảng $10^7$ phép tính, hoàn toàn dưới 1 giây nha. Thực tế còn tốn thêm thời gian cho việc gọi đệ quy, nhưng với code trên ta đã AC (Accepted) bài này rồi.
Lưu ý
Code C++ thì AC nhưng code Python thì bị TLE do Python đệ quy chạy chậm hơn rất nhiều (đệ quy sâu tới $10^5$ tầng còn có thể bị lỗi RecursionError).
Cách 3Quy hoạch động bottom-up F[i][j]
Ta đã có cách quy hoạch động top-down rồi thì ta cũng sẽ có cách bottom-up, chính là anh em sẽ tạo ra công thức truy hồi đó. Cho anh em nào đã biết cơ bản về quy hoạch động rồi thì ta có 4 bước như sau:
Bước 1 – Bài toán con
Gọi $F[i][j]$ là số dãy độ dài $i$ (khi xét $i$ phần tử đầu) thoả mãn điều kiện đề bài với phần tử cuối cùng (phần tử thứ $i$) $= j$.
Bước 2 – Bài toán cơ sở
1/ Phần tử chỉ được nằm trong khoảng từ $1$ tới $m$, nên $F[i][j]$ với $j < 1$ hoặc $j > m$ sẽ $= 0$. Để tiện nhất ta lấp đầy mảng F = 0 bằng cách khai báo mảng toàn cục (toàn bộ phần tử được khởi tạo sẵn $= 0$).
2/ Khi dãy có chiều dài $1$ ($i = 1$):
– $a[1] \ne 0$: chỉ có 1 dãy có phần tử cuối $= a[1]$, tức $F[1][a[1]] = 1$, còn lại đều $= 0$ (đã khởi tạo sẵn).
– $a[1] = 0$: có 1 dãy cho mỗi giá trị cuối $1, 2, \dots, m$, nên $F[1][j] = 1$ với $1 \le j \le m$: fill(&f[1][1], &f[1][m + 1], 1);
Bước 3 – Đáp án
$F[n][1] + F[n][2]$ $+ \dots + F[n][m]$, nhớ chia dư sau mỗi lần cộng. Nhiều bạn thắc mắc sao không cần kiểm tra phần tử thứ $n$ có xác định hay không: nếu $a[n]$ xác định thì $F[n][j] = 0$ với mọi $j \ne a[n]$ (không tồn tại dãy như thế), nên cộng luôn như trên cũng ra đúng $F[n][a[n]]$.
Bước 4 – Công thức truy hồi
1/ $a[i] \ne 0$: các $F[i][j]$ với $j \ne a[i]$ đều $= 0$ (đã khởi tạo sẵn), ta chỉ cần quan tâm $F[i][a[i]]$:
$$F[i][a[i]] = \big(F[i-1][a[i]-1] + F[i-1][a[i]] + F[i-1][a[i]+1]\big) \bmod (10^9+7)$$
2/ $a[i] = 0$: phần tử cuối $j$ có thể là $1, 2, \dots, m$, làm vòng for(j) từ $1$ tới $m$:
$$F[i][j] = \big(F[i-1][j-1] + F[i-1][j] + F[i-1][j+1]\big) \bmod (10^9+7)$$
Vậy lỡ mà $j - 1 < 1$ hoặc $j + 1 > m$ thì sao? Lúc đó chắc chắn F[i-1][j-1] hoặc F[i-1][j+1] $= 0$ vì ta khởi tạo toàn bộ mảng bằng $0$. Nhờ việc mình cộng thêm 5 lúc khai báo nên ta mới có những phần tử này nha, các bạn phải cẩn thận đó, nếu khai báo vừa đủ dùng thì F[i-1][j+1] có thể khiến code bị lỗi.
Em nhập $m$ và mảng mô tả rồi bấm Tiếp để xem bảng $F$ được lấp từng hàng (cột $0$ và cột $m + 1$ là 2 cột "đệm" luôn bằng $0$):
Ví dụ nhanh:
Code quy hoạch động bottom-up – AC
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (ll)1e9 + 7;
const int N = (int)1e5 + 5;
int a[N];
ll f[N][105];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
if(a[1]) {
f[1][a[1]] = 1;
}
else {
fill(&f[1][1], &f[1][m + 1], 1);
}
for(int i = 2; i <= n; ++i) {
if(a[i]) {
f[i][a[i]] = (f[i - 1][a[i] - 1] + f[i - 1][a[i]] + f[i - 1][a[i] + 1]) % mod;
}
else {
for(int j = 1; j <= m; ++j) {
f[i][j] = (f[i - 1][j - 1] + f[i - 1][j] + f[i - 1][j + 1]) % mod;
}
}
}
ll res = 0;
for(int j = 1; j <= m; ++j) {
res = (res + f[n][j]) % mod;
}
cout << res;
return 0;
}
import sys
MOD = 10**9 + 7
N = 10**5 + 5
a = [0] * N
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
for i in range(1, n + 1):
a[i] = arr[i - 1]
# chỉ giữ 2 hàng: hàng i và hàng i - 1 (luân phiên theo i % 2)
f = [[0] * (m + 2) for _ in range(2)]
if a[1]:
f[1][a[1]] = 1
else:
for j in range(1, m + 1):
f[1][j] = 1
for i in range(2, n + 1):
cur = i % 2
prev = 1 - cur
for j in range(m + 2):
f[cur][j] = 0
if a[i]:
x = a[i]
f[cur][x] = (f[prev][x - 1] + f[prev][x] + f[prev][x + 1]) % MOD
else:
for j in range(1, m + 1):
f[cur][j] = (f[prev][j - 1] + f[prev][j] + f[prev][j + 1]) % MOD
res = sum(f[n % 2][1:m + 1]) % MOD
print(res)
Bản Python ở trên chỉ giữ 2 hàng f[0] và f[1] dùng luân phiên theo i % 2 (hàng $i$ chỉ cần hàng $i - 1$), ý tưởng y hệt bản C++.
Không gian$O(n \cdot m)$
Thời gian$O(n \cdot m)$
Độ phức tạp vẫn giống cách top-down, nhưng code sẽ chạy nhanh hơn và ăn ít bộ nhớ hơn một chút vì không phải tốn cho việc gọi đệ quy nữa.
Cách 4Rút gọn còn mảng 1 chiều
Mình hoàn toàn có thể rút gọn từ mảng 2 chiều thành mảng 1 chiều. Việc này giúp tiết kiệm bộ nhớ hơn và code chạy nhanh hơn (truy cập mảng 1 chiều nhanh hơn mảng 2 chiều), chứ độ phức tạp thời gian thì vẫn như cách trên nha. Lúc này ta bỏ $F[i][j]$ về chỉ còn $F[j]$. Trường hợp cơ sở: nếu $a[1]$ xác định thì $F[a[1]] = 1$, ngược lại gán từ $F[1]$ tới $F[m] = 1$:
C++
if(a[1]) {
f[a[1]] = 1;
}
else {
fill(f + 1, f + m + 1, 1);
}
Python
if a[1]:
f[a[1]] = 1
else:
for j in range(1, m + 1):
f[j] = 1
Các bạn tham khảo đoạn xử lý chính trước cho dễ hình dung nha:
for i in range(2, n + 1):
if a[i]:
tmp = (f[a[i] - 1] + f[a[i]] + f[a[i] + 1]) % MOD
if a[i - 1]:
f[a[i - 1]] = 0
else:
for j in range(1, m + 1):
f[j] = 0
f[a[i]] = tmp
else:
for j in range(m, 0, -1):
preF[j] = f[j]
f[j] = (f[j - 1] + f[j] + preF[j + 1]) % MOD
$a[i]$ xác định: công thức sau khi bỏ $[i]$ là $F[a[i]]$ $= (F[a[i]-1] + F[a[i]] + F[a[i]+1]) \bmod (10^9+7)$. Nhưng các phần tử còn lại phải được gán $= 0$. Vậy ta tính vào biến tạm tmp trước. Sau đó nếu $a[i-1]$ lúc trước xác định thì chỉ có $F[a[i-1]] \ne 0$, còn lại đều bằng $0$ rồi, ta gán $F[a[i-1]] = 0$. Ngược lại nếu $a[i-1] = 0$ thì phải cho toàn bộ mảng $F = 0$ (mình dùng hàm fill). Sau tất cả ta gán $F[a[i]] = tmp$.
$a[i]$ không xác định: nếu viết $F[j] = F[j-1] + F[j] + F[j+1]$ là sai! Vòng for(j) chạy ngược nên $F[j-1]$ đúng là $F[i-1][j-1]$, $F[j]$ đúng là $F[i-1][j]$, còn $F[j+1]$ thì đã bị cập nhật thành $F[i][j+1]$ chứ không phải $F[i-1][j+1]$ ta cần. Vậy ta tạo mảng preF (previous F): trước khi cập nhật thì lưu preF[j] = F[j], để khi $j$ giảm xuống thì preF[j+1] chính là $F[i-1][j+1]$:
$$F[j] = \big(F[j-1] + F[j] + preF[j+1]\big) \bmod (10^9+7)$$
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll mod = (ll)1e9 + 7;
const int N = (int)1e5 + 5;
int a[N];
ll f[105], preF[105];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
if(a[1]) {
f[a[1]] = 1;
}
else {
fill(f + 1, f + m + 1, 1);
}
for(int i = 2; i <= n; ++i) {
if(a[i]) {
ll tmp = (f[a[i] - 1] + f[a[i]] + f[a[i] + 1]) % mod;
if(a[i - 1]) {
f[a[i - 1]] = 0;
}
else {
fill(f + 1, f + m + 1, 0);
}
f[a[i]] = tmp;
}
else {
for(int j = m; j >= 1; --j) {
preF[j] = f[j];
f[j] = (f[j - 1] + f[j] + preF[j + 1]) % mod;
}
}
}
ll res = 0;
for(int i = 1; i <= m; ++i) {
res = (res + f[i]) % mod;
}
cout << res;
return 0;
}
import sys
MOD = 10**9 + 7
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [0] + [int(v) for v in data[2:2 + n]]
f = [0] * (m + 2)
preF = [0] * (m + 2)
if a[1]:
f[a[1]] = 1
else:
for j in range(1, m + 1):
f[j] = 1
for i in range(2, n + 1):
if a[i]:
tmp = (f[a[i] - 1] + f[a[i]] + f[a[i] + 1]) % MOD
if a[i - 1]:
f[a[i - 1]] = 0
else:
for j in range(1, m + 1):
f[j] = 0
f[a[i]] = tmp
else:
for j in range(m, 0, -1):
preF[j] = f[j]
f[j] = (f[j - 1] + f[j] + preF[j + 1]) % MOD
print(sum(f[1:m + 1]) % MOD)
C++▶ Chạy tay từng dòng codeCách 4: chỉ dùng mảng 1 chiều f và preF.
Không gian thật ra là $O(n + 2m)$ (mảng a, f, preF), theo BigO là $O(n)$. Thời gian vẫn là $O(n \cdot m)$ nhưng chạy nhanh hơn rất nhiều vì giờ chỉ còn thao tác trên mảng 1 chiều. Và các bạn hoàn toàn có thể tiết kiệm bộ nhớ hơn nữa bằng việc vừa đọc vào vừa xử lý, lúc đó độ phức tạp không gian chỉ còn $O(m)$ thôi.
Ghi chú kiểm tra của mình: 4 code C++ và các bản Python của Cách 1, 2, 3 là của mình trong bài viết gốc, bản Python mảng 1 chiều của Cách 4 là mình viết thêm. Cả 8 chương trình đã được kiểm tra với 250 bộ test ngẫu nhiên ($n \le 7$, $m \le 5$, nhiều số $0$) so với chương trình vét cạn thử hết $m^n$ mảng, đều khớp. Với test lớn nhất $n = 10^5$, $m = 100$ toàn số $0$ (đáp án $879725732$): Cách 2 chạy khoảng 0.33 giây, Cách 3 khoảng 0.14 giây, Cách 4 chỉ khoảng 0.03 giây. Các bản Python: Cách 2 bị RecursionError (đệ quy quá sâu), Cách 3 và 4 mất khoảng 5–6 giây, nên nộp bài thì dùng C++ nhé.
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 😇
