Chú Tiểu Chùa Hương
Đề bài
Chùa Hương là một quần thể di tích thuộc địa phận xã Hương Sơn, huyện Mỹ Đức, thành phố Hà Nội. Chùa Hương gồm nhiều chùa chiền (đáng chú ý nhất là chùa Thiên Trù) cùng với động Hương Tích rất nổi tiếng (được mệnh danh là Nam thiên đệ nhất động).
Vào mùa lễ hội (tháng Giêng đến tháng Ba âm lịch hàng năm), chú tiểu Bờm phải làm việc khá vất vả. Hàng ngày, Bờm phải từ chùa Thiên Trù đi xuống lưng chừng núi Lão rồi từ đó leo tiếp lên gần đỉnh núi để đến động Hương Tích. Sau đó, từ động Hương Tích, Bờm quay trở về chùa Thiên Trù theo đúng con đường ban đầu. Con đường bao gồm hai đoạn dãy bậc thang lát đá với số bậc lần lượt là $M$ và $N$ (xem hình minh họa). Hành trình của Bờm như sau:
- Từ chùa Thiên Trù đi xuống lưng chừng núi Lão cũng như từ đây đi lên động Hương Tích, vì đi người không nên Bờm có thể bước qua 1, 2 hoặc 3 bậc tùy thích.
- Khi từ động Hương Tích đi xuống lưng chừng núi Lão, do phải gánh đồ (do du khách cúng dường tại động) nên Bờm chỉ có thể bước qua 1 hoặc 2 bậc đồng thời sử dụng đúng 1 lần bước qua 3 bậc tại vị trí tùy thích. Tuy nhiên, khi leo tiếp lên chùa Thiên Trù, Bờm chỉ có thể bước qua 1 hoặc 2 bậc mà thôi.
Yêu cầu: Hãy tính xem có thể có bao nhiêu cách để Bờm thực hiện một chuyến đi-về trong một ngày như vậy.
Dữ liệu vào: Gồm nhiều dòng, mỗi dòng là một cặp giá trị của $M$ và $N$ ($3 \le M, N \le 500$). Các số ghi trên cùng một dòng cách nhau ít nhất một kí tự trắng.
Kết quả: Gồm nhiều dòng, mỗi dòng là kết quả tìm được ứng với cặp giá trị của $M, N$ thuộc dòng tương ứng trong file dữ liệu vào.
3 4
4 5
10 15
20 19168
2275
321404553680
1779525767133834720Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Đề bàiTóm tắt lại cho dễ hiểu
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. Trong code bên dưới mình đọc mỗi dòng vào 2 biến n, m: $n$ là số đầu dòng (chính là $M$ trong hình – dãy bậc phía chùa), $m$ là số thứ hai ($N$ trong hình – dãy bậc phía động).
Lúc đầu chú tiểu đang ở chùa Thiên Trù. Từ chùa Thiên Trù xuống lưng chừng núi Lão có $n$ bậc thang, từ lưng chừng núi Lão lên động Hương Tích có $m$ bậc thang ($3 \le n, m \le 500$). Để dễ hình dung thì các bạn nhìn hình nhé: chùa Thiên Trù nằm ở bậc thang cao nhất bên trái, động Hương Tích nằm ở bậc thang cao nhất bên phải. Hành trình của chú tiểu sẽ chia làm 3 giai đoạn chính:
- Giai đoạn 1: từ chùa Thiên Trù chú đi xuống lưng chừng núi Lão rồi từ đó leo lên động Hương Tích. Ở giai đoạn này chú có thể bước qua 1, 2 hoặc 3 bậc tuỳ thích.
- Giai đoạn 2: từ động Hương Tích xuống lưng chừng núi Lão. Chú có thể bước qua 1 hoặc 2 bậc tuỳ thích, và “đồng thời sử dụng đúng 1 lần bước qua 3 bậc tại vị trí tùy thích”.
- Giai đoạn 3: từ lưng chừng núi Lão lên chùa Thiên Trù. Giai đoạn này chú chỉ có thể bước qua 1 hoặc 2 bậc thôi.
Ý tưởngQuy tắc nhân và đếm tay ví dụ
Mình sẽ giải thích ví dụ rồi đưa ra hướng thực hiện cơ bản trước đã nha. Ví dụ: $n = 3$, $m = 4$, số cách sẽ là $168$ cách. Mình thì không thể ngồi liệt kê 168 cách ra rồi 😅. Mà cơ sở tốt nhất để làm bài này chính là sử dụng quy tắc nhân trong các quy tắc đếm.
Công việc của mình sẽ được chia làm 4 bước:
- Bước 1: từ chùa xuống lưng chừng núi;
- Bước 2: từ lưng chừng núi lên động;
- Bước 3: từ động xuống lưng chừng núi;
- Bước 4: từ lưng chừng núi lên lại chùa.
Vậy là ta đã có cơ sở rồi, giờ thử đếm tay cho các bạn hiểu đã nhé. Ở mỗi bước, mình gọi chỗ xuất phát là bậc 0 và chỗ cần tới là bậc $N$ (với $N = n$ ở bước 1, 4 và $N = m$ ở bước 2, 3). Ví dụ ở bước 1: bậc thang cao nhất bên trái (chỗ chùa Thiên Trù) là bậc 0, $n = 3$ nên bậc thang thứ 3 là bậc 2, và coi lưng chừng núi là bậc 3.
$4 \times 7 \times 2 \times 3 = 168$
- Bước 1 (từ bậc 0 tới bậc 3, bước 1, 2 hoặc 3 bậc): $\{0 \to 3,\ 0 \to 1 \to 3,\ 0 \to 1 \to 2 \to 3,\ 0 \to 2 \to 3\}$ → 4 cách.
- Bước 2 (từ bậc 0 tới bậc 4, bước 1, 2 hoặc 3 bậc): $\{0 \to 1 \to 4,\ 0 \to 1 \to 2 \to 4,\ 0 \to 2 \to 4,\ 0 \to 1 \to 3 \to 4,\ 0 \to 1 \to 2 \to 3 \to 4,\ 0 \to 2 \to 3 \to 4,\ 0 \to 3 \to 4\}$ → 7 cách.
- Bước 3 (từ bậc 0 tới bậc 4, bước 1 hoặc 2 bậc và bắt buộc đúng 1 lần bước 3 bậc): $\{0 \to 3 \to 4,\ 0 \to 1 \to 4\}$ → 2 cách.
- Bước 4 (từ bậc 0 tới bậc 3, bước 1 hoặc 2 bậc): $\{0 \to 1 \to 3,\ 0 \to 1 \to 2 \to 3,\ 0 \to 2 \to 3\}$ → 3 cách.
Vậy tổng cộng lại theo quy tắc nhân ta sẽ có $4 \times 7 \times 2 \times 3 = 168$ cách để chú tiểu thực hiện chuyến đi và về với $n = 3$, $m = 4$. Khớp test mẫu luôn 🎉.
Chuẩn bịSố nguyên lớn (BigInt) tự cài
Trước khi vào cách vét cạn thì mình sẽ có điều này lưu ý. Bạn nào để ý vào test mẫu: ở trường hợp $n = 20$, $m = 19$ kết quả đã lên đến $1779525767133834720$, sát nút giới hạn của long long rồi. Vậy với $n, m$ lớn hơn (tới 500) thì kết quả sẽ vượt qua sức chứa của long long (thực tế với $n = m = 500$ đáp án có hơn 500 chữ số). Vậy ta cần tạo ra một kiểu dữ liệu mới có thể chứa các số cực lớn, và để làm vậy ta cần kiến thức về xử lý số nguyên lớn (cụ thể là phép $+$ và phép $\times$).
Để lưu số nguyên lớn có thể tới hàng chục nghìn chữ số thì ta sẽ dùng vector hoặc string, mỗi phần tử là 1 chữ số. Ở bài này ta dùng vector vì nó tiện cho phép nhân: typedef vector<int> bigInt;. Và để tiện tính toán, ta lưu các số từ hàng đơn vị đổ đi, tức là lưu ngược. Ví dụ số 168 hay 2275 thì trong bigInt mình sẽ lưu là $\{8, 6, 1\}$ và $\{5, 7, 2, 2\}$.
Phép cộng
Để tiện nhất thì mình dùng nạp chồng toán tử + cho 2 biến kiểu bigInt. Hiểu đơn giản là với bigInt a, b, sum thì mình hoàn toàn có thể gọi sum = a + b. Cú pháp: bigInt operator + (const bigInt &a, const bigInt &b) { ... }.
Mình để tham chiếu &a, &b để tăng tốc độ: nếu không có tham chiếu thì mỗi lần gọi nó sẽ phải copy lại cả biến a sang một biến mới, rất mất thời gian với số có cả nghìn chữ số. Và để tránh vô tình thay đổi giá trị của a, b (vì tham chiếu thì sửa trong hàm là biến ở ngoài cũng đổi theo) nên mình khai báo thêm const.
Bên trong thì mình làm y như phép cộng ở tiểu học thôi. Ví dụ $98 + 97$, trong bigInt lưu là $\{8, 9\}$ và $\{7, 9\}$. Bắt đầu từ bên trái qua: $8 + 7 = 15$, viết 5 nhớ 1. $9 + 9 + 1$ (cộng với nhớ) $= 19$, viết 9 nhớ 1. Hết số để cộng, còn nhớ 1 nên viết 1 vào → kết quả $\{5, 9, 1\}$, tức là $98 + 97 = 195$.
Thường khi cộng ta phải cân bằng cho 2 số dài bằng nhau, nhưng để tối ưu thời gian nhất (mình chấp nhận code dài hơn nha): dùng 1 vòng for từ 0 đến độ dài số ngắn hơn − 1 và cộng như bình thường; tiếp tới đi từ độ dài số ngắn hơn đến độ dài số dài hơn − 1 và chỉ cộng số dài hơn + biến nhớ. Sau cùng nếu biến nhớ vẫn còn thì thêm vào kết quả. Làm vậy thì không phải thêm số 0 để cân bằng độ dài hay xoá số 0 thừa ở đầu số:
bigInt operator + (const bigInt &a, const bigInt &b) {
bigInt sum;
int n = min((int)a.size(), (int)b.size());
int mem = 0;
for(int i = 0; i < n; ++i) {
int x = a[i] + b[i] + mem;
sum.push_back(x % 10);
mem = x / 10;
}
if(n == (int)a.size()) {
for(int i = n; i < (int)b.size(); ++i) {
int x = b[i] + mem;
sum.push_back(x % 10);
mem = x / 10;
}
}
else {
for(int i = n; i < (int)a.size(); ++i) {
int x = a[i] + mem;
sum.push_back(x % 10);
mem = x / 10;
}
}
if(mem != 0) {
sum.push_back(mem);
}
return sum;
}Phép nhân
Vì ta lưu ngược từ hàng đơn vị, nên hàng đơn vị là i = 0, hàng chục là i = 1, hàng trăm là i = 2… Phép nhân mul = a * b với $a$ có $n$ chữ số, $b$ có $m$ chữ số thì mul có tối đa $n + m$ chữ số. Vậy ta khởi tạo mul dài $n + m$, toàn số 0. Sau đó duyệt qua các cặp chữ số a[i], b[j]: cộng thêm a[i] * b[j] vào vị trí mul[i + j], rồi đẩy phần nhớ sang hàng tiếp theo mul[i + j + 1] += mul[i + j] / 10, còn hàng hiện tại thì giữ chữ số cuối mul[i + j] %= 10. Nó sẽ khá là khó hiểu, các bạn có thể nháp ra giấy (hoặc bấm chạy tay ở khung bên dưới code) sẽ dễ hình dung hơn. Cuối cùng có thể còn những vị trí $\ge 10$, ta lại đẩy nhớ một lượt: mul[i + 1] += mul[i] / 10; mul[i] %= 10;.
bigInt operator * (const bigInt &a, const bigInt &b) {
bigInt mul((int)a.size() + (int)b.size(), 0);
for(int i = 0; i < (int)a.size(); ++i) {
for(int j = 0; j < (int)b.size(); ++j) {
mul[i + j] += a[i] * b[j];
mul[i + j + 1] += mul[i + j] / 10;
mul[i + j] %= 10;
}
}
mul.push_back(0);
for(int i = 0; i < (int)mul.size() - 1; ++i) {
mul[i + 1] += mul[i] / 10;
mul[i] %= 10;
}
while(mul.back() == 0 && (int)mul.size() > 1) {
mul.pop_back();
}
return mul;
}Giải thích một số chỗ:
mul.push_back(0): vì ta duyệt qua tất cả các vị trí để cộng nhớ lên hàngi + 1, nên cần thêm 1 phần tử 0 để tránh truy cậpmul[i + 1]nằm ngoài vector. Cũng vì vậy vòng lặp ngay dưới chỉ chạy từ 0 đếnmul.size() - 2.- Vòng
whileở cuối giúp xoá các chữ số 0 vô nghĩa ở cuối vector (tức là ở đầu số), và nếu kết quả là số 0 thì xoá đến khi còn 1 phần tử.
Cách 1Vét cạn bằng đệ quy
Vậy là cơ sở để làm bài này đã xong. Giờ ta sẽ đến cách vét cạn trước nha. Thực sự thì cách vét cạn của bài này sẽ không hề dễ, bạn nào mà không nắm vững đệ quy thì xử lý sẽ rất rối, nhưng mình vẫn viết để bạn nào cần thì tham khảo. Đơn giản là ta thử mọi trường hợp có thể xảy ra: ở bước 1 đi tìm có bao nhiêu cách, cứ vậy đến khi xong bước 4, rồi nhân 4 kết quả lại. Kết quả lưu vào bigInt để tránh bị tràn.
Như ví dụ ở trên, ta đều quy về đi từ bậc 0 tới bậc $N$. Ta cần thêm 1 biến $k$ quy định cách bước:
- $k = 3$: bước tối đa 3 bậc – chính là bước 1 và bước 2.
- $k = 2$: bước tối đa 2 bậc – chính là bước 4 (và phần sau khi đã nhảy 3 bậc của bước 3).
- $k = 23$: chưa dùng lần bước 3 bậc, vẫn được bước 1, 2 bậc – chính là bước 3.
Biến $i$ cho biết ta đang ở bậc nào, và biến cnt đếm xem có bao nhiêu cách hoàn thành 1 bước (vì dùng đệ quy nên cnt phải truyền tham chiếu để thay đổi trong hàm thì ở ngoài cũng thay đổi). Hàm Try(int N, int k, int i, bigInt &cnt) đếm số cách đi từ bậc $i$ tới bậc $N$:
- Nếu
i == N: tăng biến đếm lên, vì đã có 1 cách đến bậc $N$. - Nếu không thì phải có
i < N(vì $i > N$ là đi lố, không hợp lệ). Khi đó:- Nếu
k == 23 && i + 3 <= N: ta vẫn chưa dùng lần bước 3 bậc, mà bước 3 bậc chỉ dùng được khi $i + 3 \le N$. GọiTry(N, 2, i + 3, cnt)(nhảy xong 3 bậc thì từ đó chỉ được tối đa 2 bậc). Sau đó gọiTry(N, k, i + 1, cnt)vàTry(N, k, i + 2, cnt)(vẫn $k = 23$): đi thêm 1 hoặc 2 bậc nữa rồi mới dùng bước 3 bậc cũng chả sao. Nếu sau đó $i + 3 > N$ thì chính điều kiện trên sẽ loại, tính vào trường hợp không hợp lệ nên các bạn không phải lo nha. - Nếu
k != 23: gọiTry(N, k, i + 1, cnt)rồiTry(N, k, i + 2, cnt); nếuk == 3thì gọi thêmTry(N, k, i + 3, cnt).
- Nếu
Ở hàm main ta dùng 4 biến bigInt lưu kết quả 4 bước, nhân vào rồi lưu vô biến res. Lúc in ra thì vì ta lưu ngược từ hàng đơn vị nên phải in từ cuối vector lên đầu. Còn while(cin >> n >> m): vì ta không biết đầu vào có bao nhiêu cặp $n, m$ nên dùng vòng lặp while để đọc, nó sẽ đọc liên tục đến khi nào không đọc được nữa thì dừng.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef vector<int> bigInt;
bigInt operator + (const bigInt &a, const bigInt &b) {
bigInt sum;
int n = min((int)a.size(), (int)b.size());
int mem = 0;
for(int i = 0; i < n; ++i) {
int x = a[i] + b[i] + mem;
sum.push_back(x % 10);
mem = x / 10;
}
if(n == (int)a.size()) {
for(int i = n; i < (int)b.size(); ++i) {
int x = b[i] + mem;
sum.push_back(x % 10);
mem = x / 10;
}
}
else {
for(int i = n; i < (int)a.size(); ++i) {
int x = a[i] + mem;
sum.push_back(x % 10);
mem = x / 10;
}
}
if(mem != 0) {
sum.push_back(mem);
}
return sum;
}
bigInt operator * (const bigInt &a, const bigInt &b) {
bigInt mul((int)a.size() + (int)b.size(), 0);
for(int i = 0; i < (int)a.size(); ++i) {
for(int j = 0; j < (int)b.size(); ++j) {
mul[i + j] += a[i] * b[j];
mul[i + j + 1] += mul[i + j] / 10;
mul[i + j] %= 10;
}
}
mul.push_back(0);
for(int i = 0; i < (int)mul.size() - 1; ++i) {
mul[i + 1] += mul[i] / 10;
mul[i] %= 10;
}
while(mul.back() == 0 && (int)mul.size() > 1) {
mul.pop_back();
}
return mul;
}
void Try(int N, int k, int i, bigInt &cnt) {
if(i == N) {
cnt = cnt + (bigInt){1};
}
else if(i < N) {
if(k == 23 && i + 3 <= N) {
Try(N, 2, i + 3, cnt);
Try(N, k, i + 1, cnt);
Try(N, k, i + 2, cnt);
}
else if(k != 23) {
Try(N, k, i + 1, cnt);
Try(N, k, i + 2, cnt);
if(k == 3) {
Try(N, k, i + 3, cnt);
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
while(cin >> n >> m) {
bigInt buoc1, buoc2, buoc3, buoc4;
buoc1 = buoc2 = buoc3 = buoc4 = (bigInt){0};
Try(n, 3, 0, buoc1);
Try(m, 3, 0, buoc2);
Try(m, 23, 0, buoc3);
Try(n, 2, 0, buoc4);
bigInt res = buoc1 * buoc2 * buoc3 * buoc4;
for(int i = (int)res.size() - 1; i >= 0; --i) {
cout << res[i];
}
cout << endl;
}
return 0;
}import sys
sys.setrecursionlimit(10**5)
def Try(N, k, i):
if i == N:
return 1
elif i < N:
cnt = 0
if k == 23 and i + 3 <= N:
cnt += Try(N, 2, i + 3)
cnt += Try(N, k, i + 1)
cnt += Try(N, k, i + 2)
elif k != 23:
cnt += Try(N, k, i + 1)
cnt += Try(N, k, i + 2)
if k == 3:
cnt += Try(N, k, i + 3)
return cnt
return 0
for line in sys.stdin:
line = line.strip()
if not line:
continue
n, m = map(int, line.split())
buoc1 = Try(n, 3, 0)
buoc2 = Try(m, 3, 0)
buoc3 = Try(m, 23, 0)
buoc4 = Try(n, 2, 0)
res = buoc1 * buoc2 * buoc3 * buoc4
print(res)Đánh giá độ phức tạp:
Không gian $O(1)$: tuy các biến bigInt bản chất là vector nhưng ta chỉ dùng vài biến, mỗi biến có số chữ số không nhiều nên không gian chiếm dụng không đáng kể (bỏ qua ngăn xếp đệ quy sâu tối đa $N$ tầng). Thời gian thì để tính chính xác mình cũng khó, mỗi lần đến đích chỉ cộng thêm 1 nên số lời gọi đệ quy ít nhất cũng bằng chính đáp án – tăng theo hàm mũ. Cách này chỉ ăn được những test với $n, m \le 20$ thôi. Thử nộp thì code C++ được 0.5/5 điểm còn code Python được 2.1/5 điểm.
Vậy cách trên không thể AC được rồi, tuy nhiên hãy vẫn nên cài đặt nó để sau này ta 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 nha.
Cách 2Quy hoạch động + số lớn hệ 10
Để AC được bài trên thì ta phải dùng phương pháp Quy hoạch động (Dynamic Programming): tối ưu việc đếm xem có bao nhiêu cách để hoàn thành 1 bước (bước trong 4 bước mà chú tiểu phải đi nha). Cho bạn 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: Xác định bài toán con
- $F3[i]$: số cách đi được $i$ bậc thang với 1 bước có thể bước tối đa 3 bậc.
- $F2[i]$: số cách đi được $i$ bậc thang với 1 bước có thể bước tối đa 2 bậc.
- $F23[i]$: số cách đi được $i$ bậc thang với điều kiện là đã dùng đúng 1 lần bước 3 bậc, các lần còn lại chỉ bước tối đa 2 bậc.
Bước 2: Xác định bài toán cơ sở
Xét $F3$ trước: $F3[n]$ chính là số cách đi từ chùa xuống lưng chừng núi, $F3[m]$ là số cách từ lưng chừng núi lên động. $F3[0]$ là số cách đi được 0 bậc thang, tức là ta đang đứng ở đó rồi nên $F3[0] = 1$. Lên bậc 1 chỉ có 1 cách duy nhất: $F3[1] = 1$. Lên bậc 2 có $0 \to 1 \to 2$ và $0 \to 2$: $F3[2] = 2$.
Tới $F2$: $F2[n]$ là số cách đi từ lưng chừng núi lên lại chùa. Tương tự ta có $F2[0] = 1$, $F2[1] = 1$, $F2[2] = 2$.
Giờ xét $F23$: $F23[m]$ chính là số cách đi từ động xuống lưng chừng núi theo đề bài quy định. Khi ở bậc 0, 1 hay 2 thì ta chưa thể dùng 1 lần bước 3 bậc được (từ bậc 0 bước 3 bậc thì phải tới bậc 3 mà), nên $F23[0]$ $= F23[1]$ $= F23[2]$ $= 0$.
Bước 3: Xác định đáp án của bài toán
Như phần quy tắc nhân đã nói, đáp án $=$ số cách từ chùa xuống lưng chừng núi $\times$ số cách từ lưng chừng núi lên động $\times$ số cách từ động xuống lại lưng chừng núi $\times$ số cách từ lưng chừng núi lên lại chùa:
$$res = F3[n] \times F3[m] \times F23[m] \times F2[n]$$Bước 4: Xác định công thức truy hồi
1/ Với $F3[i]$: từ những vị trí nào ta có thể tới vị trí $i$ biết 1 bước tối đa 3 bậc? Đó chính là $i - 1$, $i - 2$ và $i - 3$. Chia thành 3 trường hợp:
- Đang ở $i - 1$: chỉ cần bước 1 bậc nữa là tới $i$, nên số cách $=$ số cách tới $i - 1$.
- Đang ở $i - 2$: bước 2 bậc là tới $i$, số cách $=$ số cách tới $i - 2$. Lưu ý ta sẽ không bước 1 bậc tới $i - 1$, vì như thế sẽ bị trùng với trường hợp 1.
- Đang ở $i - 3$: tương tự, bước 3 bậc là tới $i$, số cách $=$ số cách tới $i - 3$.
2/ Với $F2[i]$: tương tự nhưng mỗi bước chỉ tối đa 2 bậc.
3/ Với $F23[i]$: vẫn tới từ $i - 1$, $i - 2$ hoặc $i - 3$, nhưng có chút khác biệt:
- Từ $i - 1$ (bước 1 bậc): để thoả điều kiện đã bước 1 lần 3 bậc thì ở vị trí $i - 1$ ta phải đã dùng rồi → $F23[i - 1]$ cách.
- Từ $i - 2$ (bước 2 bậc): tương tự → $F23[i - 2]$ cách.
- Từ $i - 3$ (bước 3 bậc): vì ta dùng bước 3 bậc ngay lần này để tới $i$, nên trước đó ta chưa dùng lần nào, tức là chỉ bước 1 hoặc 2 bậc để tới $i - 3$ → chính là $F2[i - 3]$ cách.
Giờ cần tối ưu một chút nữa: đầu vào có rất nhiều cặp $n, m$ khác nhau, không lẽ mỗi cặp lại chạy lại quy hoạch động để tính? Nó sẽ mất rất nhiều thời gian đó. Mà $3 \le n, m \le 500$, vậy sao ta không chạy quy hoạch động đến $500$ luôn một lần để có mọi trường hợp, rồi đọc cặp $n, m$ nào thì chỉ việc lấy ra thôi.
Và còn điều nữa: đi từ chùa xuống lưng chừng núi và từ lưng chừng núi lên động đều bước tối đa 3 bậc, nên thay vì tạo 2 mảng $F3$ riêng cho $n$ và $m$, ta chỉ tính một mảng $F3$ đến $F3[500]$. Tương tự $F2$ dùng chung cho bước 4 và cho công thức $F23$, còn $F23$ thì đương nhiên cần 1 mảng riêng rồi.
Minh hoạ bảng quy hoạch động
Em nhập $n$, $m$ (từ 3 đến 25 để bảng vừa màn hình) rồi bấm Tiếp để xem từng cột $i$ được tính từ những ô nào, và cuối cùng nhân 4 con số lại:
Đây là source code theo tư tưởng trên cho bạn nào cần tham khảo nha. Code C++ nộp được 4.5/5 điểm (bị TLE 10 test cuối), còn code Python thì được full điểm vì Python đã hỗ trợ sẵn số nguyên lớn (cài đặt bằng C rất nhanh) nên không cần tự cài các operator như C++, code cũng rất gọn:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef vector<int> bigInt;
bigInt operator + (const bigInt &a, const bigInt &b) {
bigInt sum;
int n = min((int)a.size(), (int)b.size());
int mem = 0;
for(int i = 0; i < n; ++i) {
int x = a[i] + b[i] + mem;
sum.push_back(x % 10);
mem = x / 10;
}
if(n == (int)a.size()) {
for(int i = n; i < (int)b.size(); ++i) {
int x = b[i] + mem;
sum.push_back(x % 10);
mem = x / 10;
}
}
else {
for(int i = n; i < (int)a.size(); ++i) {
int x = a[i] + mem;
sum.push_back(x % 10);
mem = x / 10;
}
}
if(mem) {
sum.push_back(1);
}
return sum;
}
bigInt operator * (const bigInt &a, const bigInt &b) {
bigInt mul((int)a.size() + (int)b.size(), 0);
for(int i = 0; i < (int)a.size(); ++i) {
for(int j = 0; j < (int)b.size(); ++j) {
mul[i + j] += a[i] * b[j];
mul[i + j + 1] += mul[i + j] / 10;
mul[i + j] %= 10;
}
}
mul.push_back(0);
for(int i = 0; i < (int)mul.size() - 1; ++i) {
mul[i + 1] += mul[i] / 10;
mul[i] %= 10;
}
while(mul.back() == 0 && (int)mul.size() > 1) {
mul.pop_back();
}
return mul;
}
bigInt f3[501], f2[501], f23[501];
void init() {
f3[0] = f3[1] = f2[0] = f2[1] = {1};
f3[2] = f2[2] = {2};
for(int i = 3; i <= 500; ++i) {
f3[i] = f3[i - 1] + f3[i - 2] + f3[i - 3];
f2[i] = f2[i - 1] + f2[i - 2];
}
f23[0] = f23[1] = f23[2] = {0};
for(int i = 3; i <= 500; ++i) {
f23[i] = f23[i - 1] + f23[i - 2] + f2[i - 3];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
init();
int n, m;
while(cin >> n >> m) {
bigInt res = f3[n] * f3[m] * f23[m] * f2[n];
for(int i = (int)res.size() - 1; i >= 0; --i) {
cout << res[i];
}
cout << endl;
}
return 0;
}import sys
MAX = 501
f3 = [0] * MAX
f2 = [0] * MAX
f23 = [0] * MAX
f3[0] = f3[1] = f2[0] = f2[1] = 1
f3[2] = f2[2] = 2
for i in range(3, 501):
f3[i] = f3[i - 1] + f3[i - 2] + f3[i - 3]
f2[i] = f2[i - 1] + f2[i - 2]
f23[0] = f23[1] = f23[2] = 0
for i in range(3, 501):
f23[i] = f23[i - 1] + f23[i - 2] + f2[i - 3]
for line in sys.stdin:
line = line.strip()
if not line:
continue
n, m = map(int, line.split())
res = f3[n] * f3[m] * f23[m] * f2[n]
print(res)Nếu bạn có thắc mắc về các hàm +, * của bigInt hay lý do tại sao phải in ngược kết quả thì mình đã lý giải ở phần Số nguyên lớn rồi nha.
Cách 3Gộp x[i], y[i] – mỗi truy vấn chỉ 1 phép nhân
Ở phần nhân khi đọc $n, m$ các bạn càng nhân nhiều thì sẽ càng tốn thời gian nha (phép nhân số lớn tốn hơn phép cộng rất nhiều). Vậy thì mình có thể tối ưu hơn một chút. Ta đổi chỗ các thừa số:
$$res = F3[n] \times F3[m] \times F23[m] \times F2[n] = \big(F3[n] \times F2[n]\big) \times \big(F3[m] \times F23[m]\big)$$Các bạn thấy trùng hợp chứ: vì $n, m$ chỉ có $500 - 3 + 1 = 498$ giá trị nên $F3[n] \times F2[n]$ và $F3[m] \times F23[m]$ cũng chỉ có 498 trường hợp thôi. Vậy ta đặt
Vậy với mỗi cặp $n, m$ ta chỉ phải thực hiện 1 phép nhân thay vì 3 phép nhân như trước. Giờ chỉ việc chỉnh sửa code một chút, thêm mảng x, y nữa vào là xong. Nhờ tối ưu hơn nên được 4.75/5 điểm, chỉ 5 test cuối bị TLE:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef vector<int> bigInt;
bigInt operator + (const bigInt &a, const bigInt &b) {
bigInt sum;
int n = min((int)a.size(), (int)b.size());
int mem = 0;
for(int i = 0; i < n; ++i) {
int x = a[i] + b[i] + mem;
sum.push_back(x % 10);
mem = x / 10;
}
if(n == (int)a.size()) {
for(int i = n; i < (int)b.size(); ++i) {
int x = b[i] + mem;
sum.push_back(x % 10);
mem = x / 10;
}
}
else {
for(int i = n; i < (int)a.size(); ++i) {
int x = a[i] + mem;
sum.push_back(x % 10);
mem = x / 10;
}
}
if(mem) {
sum.push_back(1);
}
return sum;
}
bigInt operator * (const bigInt &a, const bigInt &b) {
bigInt mul((int)a.size() + (int)b.size(), 0);
for(int i = 0; i < (int)a.size(); ++i) {
for(int j = 0; j < (int)b.size(); ++j) {
mul[i + j] += a[i] * b[j];
mul[i + j + 1] += mul[i + j] / 10;
mul[i + j] %= 10;
}
}
mul.push_back(0);
for(int i = 0; i < (int)mul.size() - 1; ++i) {
mul[i + 1] += mul[i] / 10;
mul[i] %= 10;
}
while(mul.back() == 0 && (int)mul.size() > 1) {
mul.pop_back();
}
return mul;
}
bigInt x[501], y[501];
void init() {
bigInt f3[501], f2[501], f23[501];
f3[0] = f3[1] = f2[0] = f2[1] = {1};
f3[2] = f2[2] = {2};
for(int i = 3; i <= 500; ++i) {
f3[i] = f3[i - 1] + f3[i - 2] + f3[i - 3];
f2[i] = f2[i - 1] + f2[i - 2];
x[i] = f3[i] * f2[i];
}
f23[0] = f23[1] = f23[2] = {0};
for(int i = 3; i <= 500; ++i) {
f23[i] = f23[i - 1] + f23[i - 2] + f2[i - 3];
y[i] = f3[i] * f23[i];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
init();
int n, m;
while(cin >> n >> m) {
bigInt res = x[n] * y[m];
for(int i = (int)res.size() - 1; i >= 0; --i) {
cout << res[i];
}
cout << endl;
}
return 0;
}import sys
MAX = 501
f3 = [0] * MAX
f2 = [0] * MAX
f23 = [0] * MAX
x = [0] * MAX
y = [0] * MAX
f3[0] = f3[1] = f2[0] = f2[1] = 1
f3[2] = f2[2] = 2
for i in range(3, MAX):
f3[i] = f3[i - 1] + f3[i - 2] + f3[i - 3]
f2[i] = f2[i - 1] + f2[i - 2]
x[i] = f3[i] * f2[i]
f23[0] = f23[1] = f23[2] = 0
for i in range(3, MAX):
f23[i] = f23[i - 1] + f23[i - 2] + f2[i - 3]
y[i] = f3[i] * f23[i]
out = []
data = sys.stdin.read().split()
for k in range(0, len(data) - 1, 2):
n, m = int(data[k]), int(data[k + 1])
out.append(str(x[n] * y[m]))
print('\n'.join(out))Cách 4Số lớn hệ cơ số 10^9 – AC
Từ cách đầu tiên ta đã tạo ra kiểu bigInt, mỗi phần tử của vector lưu 1 chữ số. Ưu điểm là dễ sử dụng và hình dung. Còn nhược điểm là vector rất dài, dẫn tới tốn bộ nhớ và đặc biệt là tốn thời gian ở các phép toán: phép cộng $a + b$ mất $O(\text{size lớn hơn})$, phép nhân $a \times b$ mất $O(\text{size}(a) \times \text{size}(b))$. Vector càng dài thì càng phải cộng và nhân nhiều hơn.
Giải pháp: mỗi phần tử của vector hãy lưu 1 đoạn của số nguyên lớn, cụ thể mỗi đoạn có nhiều nhất 9 chữ số. Ví dụ số nguyên lớn có 90 chữ số thì với cách cũ vector có size 90, phép cộng và nhân là $O(90)$ và $O(90 \cdot 90)$; còn với cách mới vector chỉ có size 10, phép cộng và nhân là $O(10)$ và $O(10 \cdot 10)$. Nhanh hơn rất nhiều rồi đúng không các bạn 😁.
Nói chút về hệ cơ số (hệ đếm): hệ cơ số 2 thì mỗi chữ số chỉ là 0 hoặc 1; hệ cơ số 10 thì mỗi chữ số từ 0 → 9. Với kiểu dữ liệu mới, mỗi "chữ số" có thể từ 0 → 999.999.999, chính là hệ cơ số $10^9$. Vì nó vẫn là 1 hệ cơ số nên các quy tắc cộng và nhân ở trên vẫn đúng, chỉ khác là trước đây cộng/nhân ra số $\ge 10$ thì viết % 10 và nhớ / 10, thì giờ ra số $\ge 10^9$ ta viết % 10^9 và nhớ / 10^9.
Ta vẫn lưu ngược nhé. Ví dụ số $987.654.321.987.654.321$ (dấu chấm cho dễ đọc thôi) có 18 chữ số: kiểu cũ lưu là $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$, kiểu mới chỉ là $\{987654321, 987654321\}$: cụm 9 chữ số tính từ hàng đơn vị là phần tử 0, cụm 9 chữ số tiếp theo là phần tử 1, …
Và vì a[i], b[j] đều có thể lên tới 9 chữ số, nhân 2 số 9 chữ số có thể ra số 18 chữ số nên dùng int sẽ bị tràn. Để an toàn ta chuyển sang typedef vector<long long> bigLL; và khai báo const ll base = (ll)1e9; để những chỗ %= base, / base chính là %= 10^9, / 10^9:
typedef long long ll;
typedef vector<ll> bigLL;
const ll base = (ll)1e9;
bigLL operator + (const bigLL &a, const bigLL &b) {
bigLL sum;
int n = min((int)a.size(), (int)b.size());
ll mem = 0;
for(int i = 0; i < n; ++i) {
ll x = a[i] + b[i] + mem;
sum.push_back(x % base);
mem = x / base;
}
if(n == (int)a.size()) {
for(int i = n; i < (int)b.size(); ++i) {
ll x = b[i] + mem;
sum.push_back(x % base);
mem = x / base;
}
}
else {
for(int i = n; i < (int)a.size(); ++i) {
ll x = a[i] + mem;
sum.push_back(x % base);
mem = x / base;
}
}
if(mem) {
sum.push_back(mem);
}
return sum;
}
bigLL operator * (const bigLL &a, const bigLL &b) {
bigLL mul((int)a.size() + (int)b.size(), 0);
for(int i = 0; i < (int)a.size(); ++i) {
for(int j = 0; j < (int)b.size(); ++j) {
mul[i + j] += a[i] * b[j];
mul[i + j + 1] += mul[i + j] / base;
mul[i + j] %= base;
}
}
mul.push_back(0);
for(int i = 0; i < (int)mul.size() - 1; ++i) {
mul[i + 1] += mul[i] / base;
mul[i] %= base;
}
while(mul.back() == 0 && (int)mul.size() > 1) {
mul.pop_back();
}
return mul;
}Cẩn thận khi in: mất số 0!
Các bạn nghĩ đến đây là đã xong rồi chứ? Bạn nào bê 2 hàm trên vào mà quên bước này nữa là Wrong Answer đó nhé. Giả sử một đoạn có $x = a[i] + b[i]$ $= 1.033.836.303$, ta viết $033.836.303$ xuống và nhớ 1 sang hàng tiếp theo. Nhưng nếu lấy x % 10^9 thì sẽ ra $33.836.303$, mất số 0 rồi. Nó không ảnh hưởng đến việc tính toán (vì cộng hay nhân với $033.836.303$ hay $33.836.303$ là như nhau), nhưng sẽ ảnh hưởng ở đoạn in kết quả.
Để ý một chút là sẽ nhận ra: mỗi phần tử lưu đủ 9 chữ số liên tiếp, chỉ có phần tử cuối cùng của vector là ngoại lệ (số có 20 chữ số thì phần tử 0 lưu 9 chữ số từ hàng đơn vị, phần tử 1 lưu 9 chữ số tiếp theo, phần tử 2 chỉ lưu 2 chữ số đầu). Vậy khi in ta in phần tử cuối vector trước, sau đó các phần tử còn lại nếu chưa đủ 9 chữ số thì phải in thêm số 0 cho đủ: có 8 chữ số thì in thêm 1 số 0, 7 chữ số thì in thêm 2 số 0, …, 1 chữ số thì in thêm 8 số 0.
Đếm xem mỗi res[i] có bao nhiêu chữ số thì rất tốn thời gian. Mẹo nhanh là so sánh res[i] lần lượt với $10^8, 10^7, \ldots, 10^1$: nếu nhỏ hơn $10^8$ (số nhỏ nhất có 9 chữ số) thì chắc chắn thiếu, in 1 số 0; nếu tiếp tục nhỏ hơn $10^7$ thì in thêm số 0 nữa; … cứ như vậy cho đến $10^1$. Ta tạo mảng e với e[i] $= 10^i$:
int e[9] = {1};
for(int i = 1; i < 9; ++i) {
e[i] = e[i - 1] * 10;
}
// khi in res[i] (trừ phần tử cuối):
for(int j = 8; j >= 1 && res[i] < e[j]; --j) {
cout << 0;
}
cout << res[i];Vòng lặp j bắt đầu so sánh res[i] với $10^8$: nếu nhỏ hơn thì in ra số 0 rồi giảm $j$ xuống 7; còn nếu $\ge 10^8$ thì không in và dừng vòng lặp. Cứ như vậy cho đến khi res[i] >= e[j] hoặc $j = 0$ thì dừng. Nhờ vòng lặp trên mà ta in được đủ các số 0 bị thiếu.
res = {133834720, 779525767, 1} (đáp án test 4):res = {33836303, 1} thì phải bù 1 số 0:Source code hoàn chỉnh (AC full điểm):
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef vector<ll> bigLL;
const ll base = (ll)1e9;
bigLL operator + (const bigLL &a, const bigLL &b) {
bigLL sum;
int n = min((int)a.size(), (int)b.size());
ll mem = 0;
for(int i = 0; i < n; ++i) {
ll x = a[i] + b[i] + mem;
sum.push_back(x % base);
mem = x / base;
}
if(n == (int)a.size()) {
for(int i = n; i < (int)b.size(); ++i) {
ll x = b[i] + mem;
sum.push_back(x % base);
mem = x / base;
}
}
else {
for(int i = n; i < (int)a.size(); ++i) {
ll x = a[i] + mem;
sum.push_back(x % base);
mem = x / base;
}
}
if(mem) {
sum.push_back(mem);
}
return sum;
}
bigLL operator * (const bigLL &a, const bigLL &b) {
bigLL mul((int)a.size() + (int)b.size(), 0);
for(int i = 0; i < (int)a.size(); ++i) {
for(int j = 0; j < (int)b.size(); ++j) {
mul[i + j] += a[i] * b[j];
mul[i + j + 1] += mul[i + j] / base;
mul[i + j] %= base;
}
}
mul.push_back(0);
for(int i = 0; i < (int)mul.size() - 1; ++i) {
mul[i + 1] += mul[i] / base;
mul[i] %= base;
}
while(mul.back() == 0 && (int)mul.size() > 1) {
mul.pop_back();
}
return mul;
}
bigLL x[501], y[501];
void init() {
bigLL f3[501], f2[501], f23[501];
f3[0] = f3[1] = f2[0] = f2[1] = {1};
f3[2] = f2[2] = {2};
for(int i = 3; i <= 500; ++i) {
f3[i] = f3[i - 1] + f3[i - 2] + f3[i - 3];
f2[i] = f2[i - 1] + f2[i - 2];
x[i] = f3[i] * f2[i];
}
f23[0] = f23[1] = f23[2] = {0};
for(int i = 3; i <= 500; ++i) {
f23[i] = f23[i - 1] + f23[i - 2] + f2[i - 3];
y[i] = f3[i] * f23[i];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
init();
int e[9] = {1};
for(int i = 1; i < 9; ++i) {
e[i] = e[i - 1] * 10;
}
int n, m;
while(cin >> n >> m) {
bigLL res = x[n] * y[m];
cout << res.back();
for(int i = (int)res.size() - 2; i >= 0; --i) {
for(int j = 8; j >= 1 && res[i] < e[j]; --j) {
cout << 0;
}
cout << res[i];
}
cout << endl;
}
return 0;
}import sys
BASE = 10 ** 9
def add(a, b): # cộng 2 số lớn lưu ngược, mỗi phần tử 9 chữ số
if len(a) < len(b):
a, b = b, a
s, mem = [], 0
for i in range(len(a)):
t = a[i] + (b[i] if i < len(b) else 0) + mem
s.append(t % BASE)
mem = t // BASE
if mem:
s.append(mem)
return s
def mul(a, b): # nhân 2 số lớn lưu ngược, hệ cơ số 10^9
r = [0] * (len(a) + len(b) + 1)
for i in range(len(a)):
for j in range(len(b)):
r[i + j] += a[i] * b[j]
r[i + j + 1] += r[i + j] // BASE
r[i + j] %= BASE
for i in range(len(r) - 1):
r[i + 1] += r[i] // BASE
r[i] %= BASE
while len(r) > 1 and r[-1] == 0:
r.pop()
return r
def to_str(a): # in phần tử cuối trước, các phần tử còn lại bù đủ 9 chữ số
return str(a[-1]) + ''.join(str(v).zfill(9) for v in reversed(a[:-1]))
MAX = 501
f3 = [[1], [1], [2]] + [None] * (MAX - 3)
f2 = [[1], [1], [2]] + [None] * (MAX - 3)
f23 = [[0], [0], [0]] + [None] * (MAX - 3)
x = [None] * MAX
y = [None] * MAX
for i in range(3, MAX):
f3[i] = add(add(f3[i - 1], f3[i - 2]), f3[i - 3])
f2[i] = add(f2[i - 1], f2[i - 2])
f23[i] = add(add(f23[i - 1], f23[i - 2]), f2[i - 3])
x[i] = mul(f3[i], f2[i])
y[i] = mul(f3[i], f23[i])
out = []
data = sys.stdin.read().split()
for k in range(0, len(data) - 1, 2):
n, m = int(data[k]), int(data[k + 1])
out.append(to_str(mul(x[n], y[m])))
print('\n'.join(out))Đánh giá độ phức tạp: gọi $D$ là số phần tử (cụm 9 chữ số) của các số lớn, $D \approx 30$ với $i = 500$ ($F3[500]$ có khoảng 132 chữ số). Phần tính sẵn chạy $500$ lần, mỗi lần vài phép cộng $O(D)$ và 2 phép nhân $O(D^2)$; mỗi truy vấn chỉ 1 phép nhân $O(D^2)$ và in ra.
Tổng kếtSo sánh 4 cách
| Cách | Ý tưởng | Mỗi truy vấn | Kết quả |
|---|---|---|---|
| 1 | Đệ quy thử mọi cách bước, cộng số lớn từng lần | hàm mũ | C++ 0.5/5, Python 2.1/5 |
| 2 | QHĐ $F3, F2, F23$ tính sẵn đến 500, số lớn hệ 10 | 3 phép nhân | C++ 4.5/5 (Python AC) |
| 3 | Gộp $x[i], y[i]$ tính sẵn | 1 phép nhân | C++ 4.75/5 |
| 4 | Như cách 3, số lớn hệ $10^9$ + bù số 0 khi in | 1 phép nhân, ngắn hơn ~9 lần | AC |
- 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