Chúng ta có thể tính số Fibonacci thứ ~n~ bằng cách tính từng ~F_j~. Tuy nhiên, với bài toán này chúng ta không thể tính toán kết quả trong thời gian cho phép với giới hạn ~n \leq 10^{18}~. Chính vì vậy chúng ta cần một công cụ Nhân ma trận để có thể giải quyết bài toán này. Bài toán tương tự ví dụ.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct Matrix {
    int a[2][2] = {{0, 0}, {0, 0}};
    Matrix operator *(const Matrix& other) const {
        Matrix product;
        for(int i : {0, 1}) {
            for(int j : {0, 1}) {
                for(int k : {0, 1}) {
                    product.a[i][k] = (product.a[i][k]
                            + (long long) a[i][j] * other.a[j][k]) % mod;
                }
            }
        }
        return product;
    }
};
Matrix expo_power(Matrix a, long long n) {
    Matrix res;
    res.a[0][0] = res.a[1][1] = 1;
    while(n) {
        if(n % 2) {
            res = res * a;
        }
        n /= 2;
        a = a * a;
    }
    return res;
}
int main() {
    long long n;
    cin >> n;
    Matrix single;
    single.a[0][0] = 0;
    single.a[0][1] = 1;
    single.a[1][0] = 1;
    single.a[1][1] = 1;
    cout << expo_power(single, n).a[1][0] << endl;
}