Qua sông
Đề bài
Nhà của Dế Mèn và trường làng cách nhau một con sông. Giữa dòng sông có $N$ hòn đá nhô lên khỏi mặt nước được đánh số từ 1 đến $N$ theo hướng từ nhà đến trường. Mỗi lần đi học, Dế Mèn phải nhảy lên các hòn đá bắt đầu từ hòn đá thứ 1 và kết thúc ở hòn đá thứ $N$ để lên bờ bên kia. Với mỗi bước nhảy, nếu đang đứng ở hòn đá thứ $x$, Dế Mèn chỉ có thể nhảy đến hòn đá thứ $x + d$, với $d$ là một số nguyên dương thuộc một trong $K$ đoạn các số nguyên dương rời nhau lần lượt là $[L_1, R_1],$ $[L_2, R_2],$ $\dots,$ $[L_K, R_K]$.
Để đảm bảo an toàn, mỗi lần sang sông đi học Dế Mèn phải đi theo một cách khác nhau. Hai cách đi là khác nhau nếu có ít nhất một bước nhảy khác nhau.
Yêu cầu: Hãy đếm số cách đi khác nhau mà Dế Mèn có thể thực hiện được.
Dữ liệu vào: Đọc từ tệp văn bản QUASONG.INP có cấu trúc như sau:
- Dòng đầu ghi hai số nguyên dương $N, K$;
- Trong $K$ dòng tiếp theo, dòng thứ $i$ $(1 \le i \le K)$ ghi hai số $L_i, R_i$ $(1 \le L_i \le R_i \le N)$;
- Các số trong tệp viết cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra tệp văn bản QUASONG.OUT gồm một số duy nhất là số cách đi khác nhau mà Dế Mèn có thể thực hiện được khi chia lấy dư cho $1\,000\,000\,007$.
Ràng buộc:
- Có 20% số điểm tương ứng với $N \le 10$ và $K = 1$;
- Có 30% số điểm tương ứng với $10 < N \le 1000$ và $K = 1$;
- Có 20% số điểm tương ứng với $1000 < N \le 10\,000$ và $1 < K \le 10$;
- Có 30% số điểm tương ứng với $10\,000 < N \le 200\,000$ và $1 < K \le 10$.
Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB.
6 1
2 325 2
1 1
3 54Giải thích:
| Ví dụ | Bước nhảy được phép | Các cách đi |
|---|---|---|
| 1 | $d \in [2, 3]$ | $1 \to 3 \to 6$ $1 \to 4 \to 6$ |
| 2 | $d \in [1, 1]$ hoặc $d \in [3, 5]$ | $1 \to 2 \to 3 \to 4 \to 5$ $1 \to 2 \to 5$ $1 \to 4 \to 5$ $1 \to 5$ |
QUASONG.INP / QUASONG.OUT. Code bên dưới dùng câu lệnh if(fopen("QUASONG.INP", "r")) { freopen(...); }: có file thì đọc/ghi file, không có file thì tự động đọc bàn phím và in ra màn hình – nộp ở đâu cũng chạy được. Nếu trên CLUE OJ không nộp được thì các bạn nộp ở link Codeforces bên dưới.Lời mở đầu
Đây là một bài đếm số cách rất điển hình của quy hoạch động: "số cách tới đích = tổng số cách tới các vị trí có thể nhảy tới đích". Bài có 4 subtask tăng dần độ khó, rất hợp để đi từng bước: đệ quy vét cạn → QHĐ bảng → QHĐ + tổng tiền tố. Mỗi cách mình đều chạy thật trên bộ test chính thức để các bạn thấy rõ cách nào ăn được subtask nào.
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 CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 20 test. Thứ tự test xen kẽ giữa các subtask (test 1, 5, 9, 13 là subtask 1; test 2, 6, 10, 14, 17, 19 là subtask 2...), mình đã đọc từng test và xếp lại theo điều kiện của đề:
| Subtask | Điều kiện (đề) | Các test | $N$ | $K$ lớn nhất | Tổng độ dài các đoạn (lớn nhất) | $N \times$ tổng độ dài (lớn nhất) |
|---|---|---|---|---|---|---|
| 1 (20%) | $N \le 10$, $K = 1$ | 1, 5, 9, 13 | 6 – 10 | 1 | 10 | 100 |
| 2 (30%) | $10 < N \le 1000$, $K = 1$ | 2, 6, 10, 14, 17, 19 | 50 – 999 | 1 | 67 | 47.952 |
| 3 (20%) | $1000 < N \le 10\,000$, $1 < K \le 10$ | 3, 7, 11, 15 | 3.254 – 9.999 | 10 | 3.458 | 34.576.542 |
| 4 (30%) | $10\,000 < N \le 200\,000$, $1 < K \le 10$ | 4, 8, 12, 16, 18, 20 | 70.000 – 200.000 | 10 | 139.604 | 27.920.800.000 |
- Mọi test đều đúng điều kiện của subtask tương ứng, các đoạn $[L_i, R_i]$ đều rời nhau như đề nói (nhờ vậy mỗi độ dài bước nhảy $d$ chỉ được đếm một lần).
- Test 20 có các đoạn không được sắp xếp theo thứ tự tăng dần (đoạn $[100000, 200000]$ đứng trước đoạn $[200, 300]$). Code nào ngầm giả sử các đoạn đã sắp xếp sẽ dễ dính bẫy ở test này.
- Cột "$N \times$ tổng độ dài" là số phép cộng của cách 2 bên dưới: ở subtask 4 lên tới hơn $10^{10}$ – quá lớn cho 1 giây.
Kết quả chạy thật của các cách bên dưới theo từng subtask:
| Subtask | Các test | Cách 1 đệ quy vét cạn | Cách 2 QHĐ $O(N \cdot \sum)$ | Cách 3 QHĐ + tổng tiền tố |
|---|---|---|---|---|
| 1 (20%) | 1, 5, 9, 13 | 4/4 | 4/4 | 4/4 |
| 2 (30%) | 2, 6, 10, 14, 17, 19 | 1/6 | 6/6 | 6/6 |
| 3 (20%) | 3, 7, 11, 15 | 0/4 | 4/4 | 4/4 |
| 4 (30%) | 4, 8, 12, 16, 18, 20 | 0/6 | 0/6 | 6/6 |
Bảng trên là bản C++ (giới hạn 1 giây). Bản Python xem ở phần tổng kết.
Ý tưởngNhìn vào bước nhảy cuối cùng
Gọi $f[i]$ là số cách đi từ hòn đá 1 tới hòn đá $i$. Hỏi: muốn đứng ở hòn đá $i$ thì bước nhảy cuối cùng xuất phát từ đâu? Nếu bước cuối dài $d$ (với $d$ thuộc một đoạn $[L_j, R_j]$) thì trước đó Dế Mèn đứng ở hòn đá $i - d$. Các bước cuối khác nhau cho các cách đi khác nhau, nên:
$$f[i] = \sum_{j=1}^{K} \ \sum_{d = L_j}^{R_j} f[i - d] \quad (\text{chỉ lấy } i - d \ge 1).$$ Đáp án là $f[N]$ (nhớ lấy dư cho $10^9 + 7$).
Ví dụ 1 ($d \in [2, 3]$): $f[1] = 1$, $f[2] = 0$ (không nhảy được 1 bước), $f[3] = f[1] = 1$, $f[4] = f[2] + f[1] = 1$, $f[5] = f[3] + f[2] = 1$, $f[6] = f[4] + f[3] = 2$ ✔.
Để ý tổng $\sum_{d=L_j}^{R_j} f[i - d]$ $= f[i - R_j] + \dots + f[i - L_j]$ là tổng của một đoạn liên tiếp trong mảng $f$ – đây chính là chìa khoá của cách 3 (tổng tiền tố). Em nhập $N$ và các đoạn rồi bấm Tiếp để xem bảng $f$ được điền dần: ô vàng là ô đang tính, các ô xanh tím là các hòn đá có thể nhảy tới nó:
Cách 1Đệ quy vét cạn – subtask 1
Cách "ngây thơ" nhất: viết hàm dem(x) = số cách đi từ hòn đá $x$ tới hòn đá $N$. Đứng ở $x$, thử mọi bước nhảy $d$ hợp lệ rồi gọi đệ quy dem(x + d), cộng hết lại. Khi $x = N$ là đã tới nơi: trả về 1 cách.
- Điều kiện
if(x + d <= n): không được nhảy quá hòn đá $N$ (nhảy quá là rơi xuống sông 😅). - Hàm này thực chất liệt kê từng cách đi một: số lần gọi hàm ít nhất bằng số cách đi. Mà số cách đi tăng theo cấp số nhân: với $d \in [1, 30]$ và $N = 50$ thì số cách đã lên tới cỡ $2^{48}$ – chạy cả năm cũng không xong.
- Nhiều lời gọi bị lặp lại: ở ví dụ 2,
dem(5)được gọi tới 4 lần,dem(4)2 lần... Em thử bấm chạy tay bên dưới sẽ thấy.
Kết quả chạy thật: Bản C++ đúng 5/20 test, quá thời gian ở test 2–4, 6–8, 10–12, 15, 17, 19, sai ở test 16, 18, 20; test đúng chạy lâu nhất 0.00s (ăn trọn subtask 1, thêm may mắn qua test 14 vì đoạn $[20, 25]$ chỉ cho rất ít cách đi; test 16, 18, 20 còn bị lỗi chạy vì đệ quy sâu hơn 100 000 tầng làm tràn ngăn xếp). Bản Python đúng 5/20 test, quá thời gian ở test 2–3, 6–7, 10–11, 15, 17, 19, sai ở test 4, 8, 12, 16, 18, 20; test đúng chạy lâu nhất 0.02s – các test lớn còn bị lỗi tràn ngăn xếp đệ quy.
Nếu thêm mảng nhớ (đệ quy có nhớ) để mỗi dem(x) chỉ tính một lần thì ta có đúng cách 2 bên dưới, chỉ khác là tính từ cuối về; mình viết luôn dạng vòng lặp cho gọn và tránh đệ quy sâu tới 200 000 tầng.
Cách 2QHĐ bảng – subtask 1, 2, 3
Tính $f[2], f[3], \dots, f[N]$ theo đúng công thức: mỗi $f[i]$ cộng các $f[i - d]$ với mọi $d$ trong các đoạn. Vì $f[i - d]$ có chỉ số nhỏ hơn $i$ nên khi tính tới $i$ thì các ô cần dùng đều đã có sẵn.
- Điều kiện
d < itrong vòng lặp tương đương $i - d \ge 1$: hòn đá trước phải tồn tại. - Lấy dư ngay sau mỗi phép cộng:
f[i]luôn nhỏ hơn $10^9 + 7$, cộng thêm một số nhỏ hơn $10^9 + 7$ vẫn vừa kiểulong long. - Số phép cộng là $N \times (\text{tổng độ dài các đoạn})$. Subtask 3: tối đa $\approx 3,5 \cdot 10^7$ phép – vẫn kịp. Subtask 4: tới $\approx 2,8 \cdot 10^{10}$ phép – quá chậm.
Kết quả chạy thật: Bản C++ đúng 14/20 test, quá thời gian ở test 4, 8, 12, 16, 18, 20; test đúng chạy lâu nhất 0.07s. Các test quá thời gian đúng là 6 test của subtask 4. Bản Python đúng 13/20 test, quá thời gian ở test 4, 8, 12, 15–16, 18, 20; test đúng chạy lâu nhất 0.67s.
Cách 3QHĐ + tổng tiền tố – full điểm
Trong cách 2, với mỗi đoạn $[L_j, R_j]$ ta cộng $f[i - R_j] + f[i - R_j + 1]$ $+ \dots + f[i - L_j]$ – tổng một đoạn liên tiếp của mảng $f$. Tổng đoạn thì dùng mảng tổng tiền tố là xong trong $O(1)$:
Với đoạn thứ $j$: $a = \max(1,\ i - R_j)$, $b = i - L_j$; nếu $a > b$ (tức $i - L_j < 1$) thì đoạn rỗng, bỏ qua.
Mảng $S$ được tính song song với $f$: vừa tính xong $f[i]$ thì $S[i] = S[i - 1] + f[i]$. Mỗi $f[i]$ chỉ còn $K$ phép tính.
max(1, i - R[j]): nếu $i - R_j < 1$ thì chỉ lấy từ hòn đá 1 (các bước nhảy dài hơn $i - 1$ không dùng được).S[b] - S[a - 1] + MOD: vì $S$ đã lấy dư nên $S[b]$ có thể nhỏ hơn $S[a - 1]$, hiệu bị âm. Cộng thêmMODrồi mới% MODđể kết quả luôn không âm (trong C++%của số âm ra số âm).- Không cần sắp xếp các đoạn: mỗi đoạn được xử lý độc lập, nên test 20 (đoạn không theo thứ tự) vẫn đúng.
Kết quả chạy thật: Bản C++ đúng 20/20 test; test đúng chạy lâu nhất 0.01s. Bản Python đúng 20/20 test; test đúng chạy lâu nhất 0.99s. Full điểm cả hai ngôn ngữ.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Đệ quy vét cạn | C++ | 5/20 | > 1s | Ăn subtask 1 (20 điểm / 100) |
| Python | 5/20 | > 1s | Ăn subtask 1; test lớn còn bị tràn ngăn xếp đệ quy (20 điểm / 100) | |
| 2. QHĐ cộng từng bước nhảy | C++ | 14/20 | > 1s | Ăn subtask 1, 2, 3 (70 điểm / 100) |
| Python | 13/20 | > 1s | Python chậm hơn nên rớt thêm 1 test subtask 3 (50 điểm / 100) | |
| 3. QHĐ + tổng tiền tố | C++ | 20/20 | 0.01s | Full điểm (100 điểm / 100) |
| Python | 20/20 | 0.99s | Full điểm (100 điểm / 100) |
Nhận xét
Đăng nhận xét