Mô Tả Mảng (CSES 1746 Array Description)
Đề 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$
3 5
2 0 23Note: 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 😇.
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.
Nộp bài trên LQDOJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Tóm tắtHiểu đề cho thật đơn giản
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:
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$:
if(x < 1 || x > m) {
return 0;
}if x < 1 or x > m:
return 02/ 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$:
if(a[n] && a[n] != x) {
return 0;
}if a[n] and a[n] != x:
return 03/ Đế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$:
if(n == 1) {
return 1;
}if n == 1:
return 1Xử 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:
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ếnresvà 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)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é.
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ềuF, phần tửF[n][x]lưu kết quả củaTry(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 đầyF = -1; sau mục điều kiện dừng, nếuF[n][x] != -1nghĩ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àoF[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)Giải thích một số chỗ trong code
return f[n][x] = (Try(…) + Try(…) + Try(…)) % mod;ở đây chính là ta gánf[n][x] = …rồi sau đó returnf[n][x].fill(&f[0][0], &f[n][m + 1], -1);đây chính là bước lấp đầy mảngFbằng $-1$. Bạn nào không biết hàmfillthì dùng vòng for vẫn được nha, độ phức tạp như nhau.
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.
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:
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);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$):
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++.
Độ 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$:
if(a[1]) {
f[a[1]] = 1;
}
else {
fill(f + 1, f + m + 1, 1);
}if a[1]:
f[a[1]] = 1
else:
for j in range(1, m + 1):
f[j] = 1Các bạn tham khảo đoạn xử lý chính trước cho dễ hình dung nha:
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;
}
}
}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
tmptrướ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àmfill). 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ảngpreF(previous F): trước khi cập nhật thì lưupreF[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)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.
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é.
Nhận xét
Đăng nhận xét