S3I8TD - Online C++ Compiler & Debugging Tool

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

#define int long long
#define endl '\n'

const int base=1000000000+7;

struct Matrix{
    int a[2][2]={0};
};

Matrix One(){
    Matrix res;
    res.a[0][0]=1;res.a[0][1]=0;
    res.a[1][0]=0;res.a[1][1]=1;
    return res;
}

Matrix Nhan(Matrix x, Matrix y){
    Matrix res;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++){
            res.a[i][j]=0;
            for(int t=0;t<2;t++)
                res.a[i][j]=(res.a[i][j]+x.a[i][t]*y.a[t][j])%base;
        }
    return res;
}

Matrix LuyThua(Matrix x,int n){
    Matrix res=One();
    while(n>0){
        if (n%2==1) res=Nhan(res,x);
        x=Nhan(x,x);
        n=n/2;
    }
    return res;
}

int n;
int kq;

int32_t main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    if (n==1 || n==2){
        cout<<1<<endl;
        return 0;
    }

    Matrix tmp; // tmp=[f(2), f(1)]
    tmp.a[0][0]=1;tmp.a[0][1]=1;

    Matrix X;
    X.a[0][0]=1;X.a[0][1]=1;
    X.a[1][0]=1;X.a[1][1]=0;

    // [F(n), F(n-1)] = [F(2), F(1)] * X^(n-2)
    X=LuyThua(X,n-2);
    tmp=Nhan(tmp,X);
    kq=tmp.a[0][0];

    cout<<kq<<endl;
    return 0;
}