题解 | 牛牛学数列5 | 矩阵运算+快速幂+运算符重载

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

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

    MatrixSq2 operator*(const MatrixSq2& other)const{
        MatrixSq2 res;
        for (int i = 0; i < 2; ++i)
            for (int k = 0; k < 2; ++k)
                for (int j = 0; j < 2; ++j)
                    res.m[i][j] += m[i][k] * other.m[k][j];
        return res;
    }

    MatrixSq2& operator*=(const MatrixSq2& other){
        *this = *this * other;
    return *this;
}
};

// 2*2矩阵快速幂
MatrixSq2 qpow(MatrixSq2 base,ull power){
    MatrixSq2 res(true);
    while(power){
        if(power&1) res*=base;
        base*=base;
        power>>=1;
    }
    return res;
}

// 矩阵+快速幂求fib(n)
ull fib(ull 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(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    ull n;cin>>n;

    cout<<fib(n)<<'\n';

    return 0;
}