Hiểu bài toán

Bài toán yêu cầu tính số Fibonacci thứ n với giá trị khởi tạo F[1] = a, F[2] = b và công thức truy hồi F[n] = F[n-1] + F[n-2]. Do kết quả có thể rất lớn (n có thể lên tới 10^9 theo ngữ cảnh đề thi thường gặp), ta chỉ cần in ra số dư của F[n] khi chia cho 2021 (F[n] mod 2021).

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

Cách Lặp cơ bản (Duyệt từ 3 đến n)

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

int main(){
    long long a, b, n;
    cin >> a >> b >> n;
    a %= 2021;
    b %= 2021;

    if (n == 1) {
        cout << a;
        return 0;
    }
    if (n == 2) {
        cout << b;
        return 0;
    }

    long long prev = a, curr = b, next;
    for (long long i = 3; i <= n; i++) {
        next = (prev + curr) % 2021;
        prev = curr;
        curr = next;
    }

    cout << curr;
    return 0;
}

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

Đây là cách tiếp cận trực tiếp nhất. Ta tính toán tuần tự các số Fibonacci từ F[3] đến F[n] bằng cách sử dụng 3 biến lưu giá trị của F[i-2], F[i-1] và F[i]. Ở mỗi bước, ta thực hiện phép cộng và lấy dư ngay lập tức để tránh tràn số. Biến a và b ban đầu cũng được chia lấy dư cho 2021 để đảm bảo các giá trị đầu vào đều nằm trong khoảng [0, 2020].

Cách Quy hoạch động với mảng

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,b,n;
    cin >> a >> b >> n;
    vector<long long>f(n+1);
    if (n>=1)  f[1] = a;
   if (n >= 2) f[2]=b;

    for (int i = 3;i<=n;i++){
        f[i] = (f[i-1]+f[i-2])%2021;
}
cout << f[n];
}

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

Phương pháp này sử dụng mảng f để lưu trữ toàn bộ dãy số Fibonacci từ 1 đến n. F[i] được tính dựa trên hai giá trị trước đó là F[i-1] và F[i-2]. Cách này dễ hình dung nhưng tốn bộ nhớ hơn so với phương pháp lặp chỉ dùng biến, đặc biệt khi n rất lớn.

Cách Ma trận Fibonacci (Nhanh)

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

const int MOD = 2021;

struct Matrix {
    long long m[2][2];
    Matrix() {
        m[0][0] = m[0][1] = m[1][0] = m[1][1] = 0;
    }
};

Matrix multiply(Matrix A, Matrix B) {
    Matrix C;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j]) % MOD;
            }
        }
    }
    return C;
}

Matrix power(Matrix A, long long p) {
    Matrix res;
    res.m[0][0] = 1; res.m[1][1] = 1; // Ma trận đơn vị
    while (p > 0) {
        if (p & 1) res = multiply(res, A);
        A = multiply(A, A);
        p >>= 1;
    }
    return res;
}

int main() {
    long long a, b, n;
    cin >> a >> b >> n;

    if (n == 1) { cout << a % MOD; return 0; }
    if (n == 2) { cout << b % MOD; return 0; }

    // Ma trận cơ sở
    Matrix T;
    T.m[0][0] = 1; T.m[0][1] = 1;
    T.m[1][0] = 1; T.m[1][1] = 0;

    // Tính T^(n-2)
    T = power(T, n - 2);

    // F[n] = T[0][0] * F[2] + T[0][1] * F[1]
    long long res = (T.m[0][0] * b + T.m[0][1] * a) % MOD;
    cout << res;
    return 0;
}

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

Đây là phương pháp tối ưu nhất. Dựa vào công thức: [[F[n]], [F[n-1]]] = [[1, 1], [1, 0]]^(n-1) * [[F[1]], [F[0]]]. Trong bài này F[1]=a, F[2]=b. Ta có thể suy ra ma trận quy hoạch. Phương pháp này dùng phép nhân ma trận và lũy thừa nhanh (bằng cách chia đôi số mũ) để tính kết quả trong thời gian logarit n. Nó hiệu quả hơn rất nhiều so với O(n) khi n lớn (ví dụ n = 10^18).

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

Bài học kinh nghiệm

• Luôn lấy số dư modulo 2021 ngay sau mỗi phép cộng để tránh tràn số và giữ giá trị nhỏ.
• Nếu n chỉ có giới hạn nhỏ (ví dụ < 10^6), phương pháp lặp O(n) là đủ và dễ code.
• Với n lớn (ví dụ > 10^9), bắt buộc phải dùng phương pháp ma trận (O(log n)).

Lỗi thường gặp

• Quên lấy dư a và b ban đầu, dẫn đến sai số ngay từ các bước tính đầu tiên.
• Khai báo biến có kiểu dữ liệu quá nhỏ (ví dụ int thay vì long long) gây tràn số trước khi chia lấy dư.
• Lặp từ 3 đến n nhưng n có thể bằng 1 hoặc 2, cần xử lý các trường hợp cơ bản này.