Editorial for ptit018: Lại là FIBONACCI

Hiểu bài toán

Bài toán yêu cầu tìm ký tự tại vị trí thứ i (tính từ 1) của xâu Fibonacci thứ n. Dãy xâu Fibonacci được định nghĩa như sau: G_1 = "A", G_2 = "B", và với k > 2, G_k = G_{k-2} + G_{k-1} (nối hai xâu lại). Do đó, độ dài của G_k là len[k] = len[k-2] + len[k-1] với len[1] = 1, len[2] = 1. Với n nhỏ hơn 93, ta có thể tính trước độ dài của các xâu. i có thể là số rất lớn (lên tới 18 chữ số), nên không thể tạo ra xâu G_n trực tiếp. Ta cần một thuật toán quy hoạch động hoặc truy hồi để giảm quy mô vấn đề.

Các cách tiếp cận

Cách Quy hoạch động đệ quy (Recursive DP)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll f[100]; // Mảng lưu độ dài
char Fibo(ll n, ll i) {
    if (n == 1) return 'A';
    if (n == 2) return 'B';
    // Nếu i nằm trong nửa đầu của G_n (tức là trong G_{n-2})
    if (i <= f[n - 2]) {
        return Fibo(n - 2, i);
    } else {
        // Nếu không, nó nằm trong G_{n-1}
        return Fibo(n - 1, i - f[n - 2]);
    }
}
int main() {
    f[1] = f[2] = 1;
    for (int i = 3; i <= 92; i++) f[i] = f[i-1] + f[i-2];
    int test; cin >> test;
    while (test--) {
        ll n, i;
        cin >> n >> i;
        cout << Fibo(n, i) << '\n';
    }
    return 0;
}

• Time Complexity: O(n) (vì độ sâu đệ quy tối đa là n)
• Space Complexity: O(n) (cho stack gọi hàm)

Phương pháp này dựa trên định nghĩa đệ quy của dãy Fibonacci. Ta tính trước độ dài của các xâu G_1 đến G_92 vào mảng f. Hàm Fibo(n, i) hoạt động như sau:

1. Nếu n là 1 hoặc 2, trả về 'A' hoặc 'B' (đáy đệ quy).
2. Kiểm tra xem vị trí i có nằm trong phần G_{n-2} hay không bằng cách so sánh i với f[n-2].
3. Nếu có (i <= f[n-2]), đệ quy vào Fibo(n-2, i).
4. Nếu không (i > f[n-2]), vị trí này nằm trong phần G_{n-1}. Ta giảm chỉ số i đi f[n-2] (để quy về vị trí tương ứng trong G_{n-1}) và đệ quy vào Fibo(n-1, i - f[n-2]).

Cách Vòng lặp (Iterative)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    vector<ll> len(95);
    len[1] = 1;
    len[2] = 1;
    for (int i = 3; i <= 92; i++) {
        len[i] = len[i-1] + len[i-2];
    }
    int T;
    cin >> T;
    while (T--) {
        int N;
        ll i;
        cin >> N >> i;
        // Giảm N về 2 hoặc 1
        while (N > 2) {
            if (i <= len[N-2]) {
                N -= 2; // Nếu i nằm trong G_{N-2}, chỉ cần xét G_{N-2}
            } else {
                i -= len[N-2]; // Nếu không, trừ đi độ dài G_{N-2} và xét G_{N-1}
                N -= 1;
            }
        }
        if (N == 1) cout << "A\n";
        else cout << "B\n";
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là phiên bản tối ưu hơn của đệ quy bằng cách sử dụng vòng lặp. Thay vì gọi hàm đệ quy, ta dùng vòng lặp while (N > 2) để thu hẹp phạm vi tìm kiếm.

• Nếu i <= len[N-2], vị trí nằm trong nửa đầu (G_{N-2}), ta chỉ cần quan tâm đến G_{N-2}. Do đó, ta giảm N đi 2 (N -= 2).
• Nếu không, vị trí nằm trong nửa sau (G_{N-1}), ta trừ đi độ dài của nửa đầu (i -= len[N-2]) và chuyển sang xét G_{N-1} (giảm N đi 1).
• Vòng lặp dừng lại khi N bằng 1 hoặc 2, khi đó ta biết ngay ký tự là 'A' hay 'B'. Phương pháp này loại bỏ overhead của đệ quy, tiết kiệm bộ nhớ stack.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Xâu Fibonacci có tính chất tự tương tự: G_n được cấu thành từ G_{n-2} và G_{n-1}. Điều này cho phép ta chia đôi vấn đề (divide and conquer) mà không cần tạo ra xâu.
• Vì N nhỏ (< 93) nhưng i rất lớn, ta cần tính trước độ dài của các xâu Fibonacci (sử dụng long long vì độ dài có thể lên tới ~10^19) thay vì cố gắng sinh xâu.
• Bài toán có thể giải quyết bằng cả đệ quy và vòng lặp. Vòng lặp thường hiệu quả hơn về bộ nhớ và tránh tràn stack với N lớn.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu sai cho độ dài: int hoặc unsigned int sẽ bị tràn số (overflow) khi tính toán cho n lớn (khoảng n=92 độ dài xâu ~7.5e18). Phải dùng long long (trong C++) hoặc long long (trong C).
• Lỗi logic trong đệ quy/ vòng lặp: Nhầm lẫn giữa G_{n-1} và G_{n-2}. Phải nhớ rằng G_n = G_{n-2} + G_{n-1}, nên nửa đầu là G_{n-2}.
• Quên xử lý trường hợp cơ sở: Vòng lặp chỉ giảm N về 1 hoặc 2, sau đó phải có câu lệnh if/else để in ra 'A' hoặc 'B'.