Tiếp tục seri :D $\\$ Sau khi học về số Fibonaccy, KD đã định nghĩa thêm một loại số dựa trên số Fibonaccy như sau: Fibo_KD(1) = Fibo_KD(2) = 1 Fibo_KD(n) = Fibo_KD(n-1) + Fibo_KD(n-2) + 1 (với n >= 3) KD muốn biết số thứ `N` trong định nghĩa số Fibo_KD của mình là bao nhiêu, do kết quả có thể rất lớn nên KD chỉ cần bạn in ra 9 chữ số cuối cùng trong kết quả. $\\$ Input: - Dòng đầu tiên gồm số `T`: Số test - `T` dòng tiếp theo mỗi dòng gồm một số `N`. Output: - Gồm `T` dòng tương ứng với kết quả của mỗi test. Ví dụ: Sample Input: 3 1 2 3 Sample Output: 1 1 3 $\\$ Subtask: - 10%: `1 <= T <= 10^5` ; `1 <= N <= 10^6`. - 90%: `1 <= T <= 10^5` ; `1 <= N <= 10^18`.

Thuật toán

Ta sẽ dùng thuật toán nhân ma trận cho bài này.

Gọi số Fibo_KD thứ $n$ là $f(n)$

Giả sử ta đã tính được một ma trận $A = \left[\begin{array}{c}f(n-1)\\f(n)\\1\end{array}\right]$ và ta cần tìm một ma trận $B$ nào đó để $BA = C = \left[\begin{array}{c}f(n)\\f(n+1)\\1\end{array}\right]$

Dựa vào định nghĩa phép nhân ma trận, ta có thể tính được 

$B = \left[\begin{array}{ccc}0&1&0\\1&1&1\\0&0&1\end{array}\right]$

Do đó, với ma trận $A$ ban đầu có $n=2$, để tìm được $f(N)$ cần tính ta cần tính ma trận kết quả của $B^{N-1}A$.

Để phép lũy thừa ma trận $B^{N-1}$ hiệu quả, ta sẽ dùng thuật toán lũy thừa nhị phân.

Độ phức tạp của thuật toán này là $O(T \times 3^3 \text{ log } N)$ với $3^3$ là chi phí nhân ma trận.

Code (C++)

#include <bits/stdc++.h>
#define ll long long
#define f1(i,n) for(ll i=1;i<=n;i++)
using namespace std;
const ll maxn = 1e6+5,mod=1e9,sz=3;

struct Mat{
    ll a[sz+1][sz+1];

    Mat(){}

    Mat(const vector<vector<ll>> &d){
        f1(i,sz) f1(j,sz) a[i][j] = d[i-1][j-1];
    }

    Mat operator *(Mat obj){
        Mat res;
        f1(i,sz) f1(j,sz) {
            res.a[i][j] = 0;
            f1(k,sz){
                res.a[i][j] = (res.a[i][j] + a[i][k] * obj.a[k][j]) % mod;
            }
        }
        return res;
    }
};

Mat powmat(Mat obj, ll ep){
    if(ep == 0){
        Mat tmp;
        f1(i,2) tmp.a[i][i] = 1;
        return tmp;
    }
    if(ep == 1) return obj;
    Mat t = powmat(obj, ep/2);
    if(ep % 2) return t*t*obj;
    else return t*t;
}

ll n,t,ans;
Mat mymat, resm;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> t;
    while(t--){
        cin >> n;
        if(n <= 2){
            cout << "1\n";
            continue;
        }
        mymat = Mat({{0,1,0},{1,1,1},{0,0,1}});
        resm = Mat({{1,0,0},{1,0,0},{1,0,0}});
        resm = powmat(mymat, n-1) * resm;
        ans = resm.a[1][1];
        cout << ans << '\n';
    }
    return 0;
}