矩阵快速幂模板

第一次写关于模板的博客，可能是心血来潮吧。

矩阵相乘代码：

void Matrix(int (&a)[2][2],int b[2][2]){
    int tmp[2][2] = {0};
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            for(int k = 0; k < 2; ++k)
                tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % N;
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            a[i][j] = tmp[i][j];
}

 普通快速幂代码：

//快速幂 (a^b)%mod
//如果求逆元，则b = mod-2;
ll pow_quick(ll a,ll b){
    ll r = 1,base = a;
    while(b){
        if(b & 1){
            r *= base;
            r %= mod;
        }
        base *= base;
        base %= mod;
        b >>= 1;
    }
    return r;
}

矩阵快速幂代码：

//矩阵快速幂定义全局变量
const ll maxn=1000+10;
const ll mod=1000000007;
const ll N = 2;
ll n = 0;
//定义一个矩阵
struct Matrix {
    ll m[N][N];
};

//矩阵相乘
Matrix multi(Matrix a,Matrix b) {
    Matrix c;
    for(ll i=0; i<N; i++) {
        for(ll j=0; j<N; j++) {
            c.m[i][j]=0;
            for(ll k=0; k<N; k++){
                c.m[i][j] += a.m[i][k]*b.m[k][j]%mod;
            }
            c.m[i][j]%=mod;
        }
    }
    return c;
}

//矩阵快速幂
Matrix power(Matrix A,ll k) {
    Matrix ans,p=A;
    re(ans.m,0);
    for(ll i = 0; i < N; i ++){
        ans.m[i][i] = 1;
    }
    while(k) {
        if(k&1) {
            ans=multi(ans,p);
            k--;
        }
        k>>=1;
        p=multi(p,p);
    }
    return ans;
}
int main() {
    ll n;
    while(~scanf("%lld",&n)) {
        Matrix A = {
            1,1,
            1,0
        };
        Matrix ans =power(A,n-1);
        printf("%lld
",ans.m[0][0]);
    }
    return 0;
}

关于斐波那契数列推广的一个公式：