Hướng dẫn giải của Matrix Exponentiation - Fibonacci


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.

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;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.