Hiểu bài toán

Bài toán yêu cầu tìm số thứ N trong một dãy số được định nghĩa với các quy tắc sinh cụ thể:

• T[0] = 0
• T[1] = 1
• T[2] = 1
• Với i >= 3:
  • Nếu i là số lẻ: T[i] = T[i-1] + T[i-2]
  • Nếu i là số chẵn: T[i] = T[i-1] - 1

Đầu vào gồm Q truy vấn, mỗi truy vấn yêu cầu tìm T[N] với N nằm trong khoảng [1, 127]. Các giá trị T[N] có thể rất lớn (lên đến hàng chục tỷ tỷ), do đó cần sử dụng kiểu dữ liệu 64-bit (long long).

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

Cách Tính toán trực tiếp (Precomputation)

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long T[128];
    T[0] = 0; T[1] = 1; T[2] = 1;
    for (int i = 3; i <= 127; i++) {
        if (i % 2 == 1) { // Số lẻ
            T[i] = T[i-1] + T[i-2];
        } else { // Số chẵn
            T[i] = T[i-1] - 1;
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        cout << T[n] << "\n";
    }
}

• Time Complexity: O(127 + Q)
• Space Complexity: O(128)

Đây là cách tiếp cận trực tiếp và hiệu quả nhất cho bài toán này. Ta tạo một mảng T lưu trữ tất cả các giá trị T[i] cho i từ 0 đến 127. Ta tính toán các giá trị này một lần duy nhất trước khi xử lý các truy vấn. Vòng lặp for chạy từ 3 đến 127 để điền vào mảng dựa trên quy tắc của bài toán. Sau đó, mỗi truy vấn chỉ cần truy cập mảng để lấy giá trị đã được tính sẵn. Độ phức tạp thời gian là O(127) để xây dựng mảng và O(Q) để trả lời truy vấn. Độ phức tạp không gian là O(128) để lưu trữ mảng.

Cách Đệ quy có nhớ (Memoization)

#include <bits/stdc++.h>
using namespace std;

long long memo[128];

long long T(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n == 2) return 1;

    if (memo[n] != -1) return memo[n];

    if (n % 2 == 1) { // Số lẻ
        return memo[n] = T(n-1) + T(n-2);
    } else { // Số chẵn
        return memo[n] = T(n-1) - 1;
    }
}

int main() {
    memset(memo, -1, sizeof(memo));

    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        cout << T(n) << "\n";
    }
}

• Time Complexity: O(127 + Q)
• Space Complexity: O(128)

Cách tiếp cận này sử dụng đệ quy kết hợp với kỹ thuật 'memoization' (lưu trữ kết quả tính toán). Hàm T(n) sẽ gọi đệ quy để tính giá trị, nhưng trước khi tính, nó kiểm tra xem giá trị đó đã được tính và lưu trong mảng memo chưa. Nếu rồi thì trả về luôn, nếu chưa thì tính và lưu lại. Với Q truy vấn, các giá trị sẽ được tính toán và lưu trữ trong lần gọi đầu tiên, các lần sau sẽ lấy từ mảng. Độ phức tạp tương tự cách 1, nhưng cách này thể hiện tư duy đệ quy, trong khi cách 1 (duyệt tuần tự) thường hiệu quả hơn một chút về mặt bộ nhớ stack và tốc độ do tránh các cuộc gọi hàm đệ quy.

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

Bài học kinh nghiệm

• Các giá trị N bị giới hạn (N <= 127), cho phép precompute (tính toán trước) toàn bộ dãy và lưu vào mảng.
• Sử dụng long long là bắt buộc vì giá trị dãy tăng rất nhanh và vượt quá giới hạn của int (ví dụ T[120] ~ 2.88e17).
• Quy tắc sinh chia rẽ rõ ràng theo tính chẵn/lẻ của chỉ số, giúp việc cài đặt vòng lặp điều kiện khá đơn giản.

Lỗi thường gặp

• Sử dụng biến kiểu int hoặc unsigned int để lưu kết quả会导致 overflow (số quá lớn so với dung lượng lưu trữ) vì các số đầu ra rất lớn.
• Quên khởi tạo mảng cho các trường hợp cơ bản (T[0], T[1], T[2]) hoặc truy cập sai chỉ số mảng.
• Nếu cài đặt đệ quy không có memoization, độ phức tạp thời gian sẽ là hàm mũ (exponential) và không thể chạy được với N lên tới 127.