Hướng dẫn giải của Xâu FIBONACCI 2
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
,
Editorial for fib2: Xâu FIBONACCI 2
Hiểu bài toán
Bài toán yêu cầu đếm số lượng ký tự 'a' trong k ký tự đầu tiên của xâu Fibonacci thứ n (Fn). Xâu Fibonacci được định nghĩa: F0 = 'a', F1 = 'b', và Fn = F{n-2} + F{n-1} cho n > 1. Dãy xâu này tăng trưởng rất nhano (theo dãy Fibonacci), nên độ dài Fn có thể rất lớn (lên tới ~10^9) với n tối đa là 45. Do đó, ta không thể tạo ra xâu Fn đầy đủ mà cần một cách tiếp cận tối ưu hơn để tính toán trên các phần của xâu.
Các cách tiếp cận
Cách Quy hoạch động phân tách đệ quy (Recursive Decomposition)
#include <bits/stdc++.h>
using namespace std;
long long len[50];
long long cntA[50];
// Precompute lengths and counts of 'a' for F_i
void precompute() {
len[0] = 1; cntA[0] = 1;
len[1] = 1; cntA[1] = 0;
for(int i = 2; i <= 45; ++i) {
len[i] = len[i-1] + len[i-2];
cntA[i] = cntA[i-1] + cntA[i-2];
}
}
long long solve(int n, long long k) {
if (n <= 1) {
if (n == 0) return 1; // F_0 = 'a'
if (n == 1) return 0; // F_1 = 'b'
}
if (k == 0) return 0;
// F_n = F_{n-2} + F_{n-1}
// Nếu k nằm trong phần F_{n-2}
if (k <= len[n-2]) {
return solve(n-2, k);
}
// Nếu k nằm trong phần F_{n-1}
else {
// Toàn bộ F_{n-2} được bao gồm, cộng với phần đầu F_{n-1}
return cntA[n-2] + solve(n-1, k - len[n-2]);
}
}
int main() {
precompute();
int T; cin >> T;
while(T--) {
int n;
long long k;
cin >> n >> k;
cout << solve(n, k) << "\n";
}
return 0;
}
- Time Complexity: O(n) mỗi truy vấn
- Space Complexity: O(n) (mảng tiền tính)
Giải pháp này dựa trên cấu trúc đệ quy của Fn. Fn = F{n-2} + F{n-1}. Để tìm số lượng 'a' trong k ký tự đầu của F_n:
- Nếu k <= độ dài của F{n-2}, bài toán quy về tìm số 'a' trong k ký tự đầu của F{n-2}.
- Nếu k > độ dài của F{n-2}, kết quả bằng toàn bộ số 'a' trong F{n-2} cộng với số 'a' trong (k - len[n-2]) ký tự đầu của F{n-1}. Ta tiền tính mảng độ dài và số 'a' cho các xâu từ F0 đến F_45 để tra cứu nhanh. Độ sâu đệ quy tối đa là n, rất nhỏ (n <= 45).
Cách Vòng lặp (Iterative Decomposition)
#include <iostream>
#include <vector>
using namespace std;
int main() {
// Precompute lengths and counts
long long len[46];
long long cntA[46];
len[0] = 1; cntA[0] = 1;
len[1] = 1; cntA[1] = 0;
for(int i = 2; i <= 45; ++i) {
len[i] = len[i-1] + len[i-2];
cntA[i] = cntA[i-1] + cntA[i-2];
}
int T;
cin >> T;
while(T--) {
int n;
long long k;
cin >> n >> k;
long long ans = 0;
while(k > 0) {
// Tìm độ dài lớn nhất của F_i không vượt quá k
// Bắt đầu từ n và giảm dần
int i = n;
// Lặp để tìm i sao cho len[i] <= k < len[i+1]
// Hoặc đơn giản là dùng điều kiện
while(i >= 2 && len[i] > k) {
i--;
}
// Nếu F_i là 'a' (i=0) hoặc 'b' (i=1)
if (i == 0) {
ans += k; // F_0 là 'a', k=1
break;
}
if (i == 1) {
// F_1 là 'b', không thêm 'a', nhưng có thể phần còn lại
// Nếu k > 1 thì lỗi logic, nhưng F_1 length 1
// Thực tế, vòng lặp sẽ giảm i về 0 nếu k=1
break;
}
// F_i = F_{i-2} + F_{i-1}
// Nếu k nằm trong F_{i-2}
if (k <= len[i-2]) {
n = i - 2;
// k giữ nguyên
} else {
// Bao gồm toàn bộ F_{i-2}
ans += cntA[i-2];
k -= len[i-2];
n = i - 1;
}
}
cout << ans << "\n";
}
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(1)
Đây là phiên bản không đệ quy của cách tiếp cận đầu tiên. Thay vì gọi hàm đệ quy, ta sử dụng vòng lặp while để mô phỏng quá trình phân tách. Biến n và k được cập nhật trong vòng lặp cho đến khi k trở nên rất nhỏ. Cách này tránh được nguy cơ tràn bộ nhớ stack (dù trong bài này không đáng kể) và có thể hiệu quả hơn một chút về mặt hiệu năng.
Cách Tối ưu hóa Tra cứu Index (Binary Search Optimization)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long len[50];
long long cntA[50];
void precompute() {
len[0] = 1; cntA[0] = 1;
len[1] = 1; cntA[1] = 0;
for(int i = 2; i <= 45; ++i) {
len[i] = len[i-1] + len[i-2];
cntA[i] = cntA[i-1] + cntA[i-2];
}
}
int main() {
precompute();
int T;
cin >> T;
while(T--) {
int n;
long long k;
cin >> n >> k;
long long ans = 0;
while(k > 0 && n > 1) {
// Tìm độ dài lớn nhất của F_x <= k và x <= n
// Sử dụng binary search để tìm index nhanh hơn
// Hoặc đơn giản là dùng lower_bound/upper_bound
// Ở đây ta chỉ cần tìm x sao cho len[x] <= k
// Do len là dãy tăng, ta có thể dùng std::upper_bound
// Lấy phần F_i phù hợp nhất
// Duyệt ngược từ n về 0 để tìm i thỏa mãn len[i] <= k
// Hoặc dùng binary search trong mảng len[0...n]
int low = 0, high = n;
int best_i = 0;
while(low <= high) {
int mid = (low + high) / 2;
if(len[mid] <= k) {
best_i = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (best_i <= 1) {
if(best_i == 0) ans += k;
break;
}
// F_{best_i} = F_{best_i-2} + F_{best_i-1}
if (k <= len[best_i-2]) {
n = best_i - 2;
} else {
ans += cntA[best_i-2];
k -= len[best_i-2];
n = best_i - 1;
}
}
cout << ans << "\n";
}
return 0;
}
- Time Complexity: O(log n) mỗi bước (tổng O(n log n) nhưng n nhỏ)
- Space Complexity: O(1)
Cách tiếp cận này giống về logic với hai cách trên nhưng tối ưu bước tìm xâu F_i có độ dài lớn nhất nhỏ hơn hoặc bằng k. Thay vì duyệt tuyến tính giảm dần từ n, ta dùng tìm kiếm nhị phân (binary search) để tìm ra chỉ số i này nhanh chóng. Tuy nhiên, do n rất nhỏ (<= 45), sự cải thiện này không đáng kể về thời gian chạy nhưng là một bài tập tốt về kỹ thuật tối ưu hóa.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n) mỗi truy vấn | O(n) (mảng tiền tính) | Quy hoạch động phân tách đệ quy (Recursive Decomposition) |
| 2 | O(n) | O(1) | Vòng lặp (Iterative Decomposition) |
| 3 | O(log n) mỗi bước (tổng O(n log n) nhưng n nhỏ) | O(1) | Tối ưu hóa Tra cứu Index (Binary Search Optimization) |
Bài học kinh nghiệm
- Sử dụng tính chất đệ quy Fn = F{n-2} + F_{n-1} để chia nhỏ bài toán thay vì thao tác trực tiếp lên xâu.
- Tiền tính độ dài và số lượng 'a' cho các xâu Fibonacci từ F0 đến F45 để tra cứu O(1) trong quá trình giải quyết mỗi test case.
- Bài toán có thể được giải quyết bằng cách mô phỏng quá trình phân tách xâu Fn thành các xâu con nhỏ hơn cho đến khi chạm tới F0 hoặc F_1.
Lỗi thường gặp
- Quên xử lý trường hợp đặc biệt khi k=0 hoặc n=0, n=1.
- Sử dụng kiểu dữ liệu sai: Độ dài xâu F_45 là Fibonacci(46) ~ 1.8e9, vượt quá giới hạn của kiểu int (2e9). Cần dùng long long.
- Lỗi logic trong việc chia tách: Cần đảm bảo rằng khi chia đôi Fn, phần đầu tiên luôn là F{n-2} và phần thứ hai là F_{n-1}.
Bình luận