题解 | 牛牛学数列5

#include <iostream>

using namespace std;
using ll = long long;

// 2*2方阵
struct MatrixSq2{
    ll m[2][2];
    MatrixSq2(){m[0][0]=m[0][1]=m[1][0]=m[1][1]=0;}
};

// 2*2矩阵乘法
MatrixSq2 mul(MatrixSq2 a,MatrixSq2 b){
    MatrixSq2 res;
    for(int i=0;i<2;++i){
        for(int j=0;j<2;++j){
            for(int k=0;k<2;++k){
                res.m[i][j]+=a.m[i][k]*b.m[k][j];
            }
        }
    }
    return res;
}

// 2*2矩阵快速幂
MatrixSq2 qpow(MatrixSq2 base,ll power){
    MatrixSq2 res;
    res.m[0][0]=res.m[1][1]=1;
    while(power){
        if(power&1) res=mul(res,base);
        base=mul(base,base);
        power>>=1;
    }
    return res;
}

// 矩阵+快速幂求fib(n)
ll fib(ll n){
    if(n==1 || n==2) return 1;
    MatrixSq2 base;
    base.m[0][0]=1;base.m[0][1]=1;
    base.m[1][0]=1;base.m[1][1]=0;
    MatrixSq2 mat=qpow(base,n-2);
    return mat.m[0][0]+mat.m[0][1];
}

int main(){
    ll n;
    cin>>n;
    cout<<fib(n)<<"\n";
    return 0;
}