题解 | 牛牛学数列5 | 矩阵乘法+快速幂优化

#include <iostream>
#include <array>
using namespace std;
using ll = long long;

// 2*2方阵
struct MatrixSq2{
    array<array<ll,2>,2> m{};
    MatrixSq2(bool isIdentity=false){
        if(isIdentity) m[0][0]=m[1][1]=1;
    }
};

// 2*2矩阵乘法
MatrixSq2 mul(const MatrixSq2& a,const 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;
}