Hướng dẫn giải của QUA SÔNG _QH
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán đếm số đường đi từ vị trí 1 đến vị trí n trên một trục số. Từ một vị trí i, ta có thể nhảy đến các vị trí i + x, trong đó x nằm trong một hoặc nhiều khoảng [lj, rj] cho trước. Yêu cầu tính số cách đi từ 1 đến n modulo 10^9 + 7. Dữ liệu: n ≤ 10^6, k ≤ 100.
Các cách tiếp cận
Cách Quy hoạch động cơ bản
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n, k;
int dp[N], pre[N];
int l[105], r[105];
int add(int a, int b) {
return (a + b) % mod;
}
int sub(int a, int b) {
return ((a - b) % mod + mod) % mod;
}
main() {
freopen("QUASONG.inp", "r", stdin);
freopen("QUASONG.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= k; i++)
cin >> l[i] >> r[i];
dp[1] = 1;
pre[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= k; j++) {
int left = max((int)0, i - r[j]);
int right = max((int)0, i - l[j]);
// dp[i] += sum(dp[left+1...right])
// sum(dp[1...right]) - sum(dp[1...left])
int sum_right = pre[right];
int sum_left = pre[left];
dp[i] = add(dp[i], sub(sum_right, sum_left));
}
pre[i] = add(pre[i - 1], dp[i]);
}
cout << dp[n];
}
- Time Complexity: O(n * k)
- Space Complexity: O(n + k)
Sử dụng quy hoạch động. dp[i] là số cách để đến vị trí i. Để tính dp[i], ta xét tất cả các khoảng nhảy [lj, rj]. Nếu ta có thể nhảy từ vị trí x đến i, thì x phải nằm trong khoảng [i - rj, i - lj]. Tổng số cách từ các vị trí này có thể tính nhanh bằng cách sử dụng mảng cộng dồn (prefix sum) pre[]. Cụ thể, dp[i] += pre[i - lj] - pre[i - rj - 1]. Độ phức tạp là O(n*k) do lặp qua n vị trí và với mỗi vị trí, lặp qua k khoảng.
Cách Quy hoạch động tối ưu với mảng cộng dồn
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n, k;
int dp[N], pre[N];
int l[105], r[105];
int add(int a, int b) {
return (a + b) % mod;
}
int sub(int a, int b) {
return ((a - b) % mod + mod) % mod;
}
main() {
freopen("QUASONG.inp", "r", stdin);
freopen("QUASONG.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= k; i++)
cin >> l[i] >> r[i];
dp[1] = 1;
pre[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= k; j++) {
int left = max((int)0, i - r[j]);
int right = max((int)0, i - l[j]);
if (right == 0) continue; // Nếu right = 0, không có vị trí nào hợp lệ
dp[i] = add(dp[i], sub(pre[right], pre[left]));
}
pre[i] = add(pre[i - 1], dp[i]);
}
cout << dp[n];
}
- Time Complexity: O(n * k)
- Space Complexity: O(n + k)
Cách tiếp cận này giống hệt cách 1, nhưng giải thích chi tiết hơn về việc tối ưu hóa tính toán tổng. Thay vì lặp lại các giá trị dp trong khoảng [i - rj, i - lj], ta duy trì một mảng pre[] là tổng tiền tố của dp[]. Khi đó, tổng các dp[x] trong khoảng [L, R] (với L = i - rj, R = i - lj) được tính bằng pre[R] - pre[L-1]. Điều này giảm độ phức tạp từ O(nklen_interval) xuống O(n*k). Đây là phương pháp chuẩn để giải quyết bài toán này với dữ liệu cho phép.
Cách Quy hoạch động với xử lý mảng cộng dồn trực tiếp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n, k;
int dp[N], diff[N]; // diff là mảng chênh lệch để cập nhật dp
int l[105], r[105];
int add(int a, int b) {
return (a + b) % mod;
}
int sub(int a, int b) {
return ((a - b) % mod + mod) % mod;
}
main() {
freopen("QUASONG.inp", "r", stdin);
freopen("QUASONG.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= k; i++)
cin >> l[i] >> r[i];
dp[1] = 1;
// diff[1] = 1; // dp[1] co dinh
// Khoi tao cho dp[2...n]
// Vong lap tinh dp[i] tu i=2 den n
// Cach khac: dung mang tien to nhu Solution 1 va 2
// Day la cach tiep can giong Solution 1 va 2 nhat, chi khac ten bien
vector<int> pre(n + 2, 0);
pre[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= k; j++) {
int L = i - r[j];
int R = i - l[j];
if (R < 1) continue;
L = max(L, 1LL);
dp[i] = add(dp[i], sub(pre[R], pre[L - 1]));
}
pre[i] = add(pre[i - 1], dp[i]);
}
cout << dp[n];
}
- Time Complexity: O(n * k)
- Space Complexity: O(n + k)
Đây là cách tiếp cận logic được implement trong các solution mẫu. Biến 'pre' đóng vai trò là mảng cộng dồn của dp. Ban đầu pre[1] = dp[1] = 1. Với mỗi i từ 2 đến n, ta tính dp[i] bằng cách lấy tổng các dp[j] thỏa mãn điều kiện nhảy. Vì dp[i] = sum(dp[x]) với x thuộc [i - rj, i - lj] (với mỗi j), ta có thể tính tổng này nhanh chóng bằng pre[R] - pre[L-1]. Cuối cùng, cập nhật pre[i] = pre[i-1] + dp[i] để sử dụng cho các bước sau.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n * k) | O(n + k) | Quy hoạch động cơ bản |
| 2 | O(n * k) | O(n + k) | Quy hoạch động tối ưu với mảng cộng dồn |
| 3 | O(n * k) | O(n + k) | Quy hoạch động với xử lý mảng cộng dồn trực tiếp |
Bài học kinh nghiệm
- Bài toán có cấu trúc quy hoạch động rõ ràng: dp[i] phụ thuộc vào các dp[j] với j < i.
- Việc sử dụng mảng cộng dồn (prefix sum) là chìa khóa để tối ưu hóa việc tính tổng các giá trị dp trong một khoảng, giảm độ phức tạp từ O(n) xuống O(1) cho mỗi truy vấn tổng.
- Với mỗi vị trí i, ta có thể đến i từ các vị trí i - x, trong đó x nằm trong khoảng [lj, rj]. Do đó, các vị trí nguồn (source) cho i nằm trong khoảng [i - rj, i - lj].
Lỗi thường gặp
- Sai lệch chỉ số khi tính toán khoảng [i - rj, i - lj]. Cần đảm bảo các chỉ số không âm và không vượt quá biên của mảng.
- Quên xử lý modulo dẫn đến số quá lớn (overflow), đặc biệt khi tính tổng.
- Lỗi truy cập ngoài biên mảng khi i - r[j] hoặc i - l[j] âm hoặc bằng 0. Cần clamp giá trị về 0 hoặc 1 tùy theo logic xử lý.
Bình luận