整数快速幂

传统情况下求解整数快速幂，需要使用一个for循环，不断乘，循环n-1次

整数快速幂的思路在于x^(m+n) = x^(n) * x^(m)，以此通过不断将原始整数累乘，这里设定幂依次为1，2，4，8……可以看到正好为二进制进位，因此利用将次数转为二进制编码，如9的二进制编码应为1001，来简化计算过程

以下是代码：

int quickpow(int x,int n){
    int res = x;
    int ans = 1;
    while(n){
        if(n&1){
            ans = ans * res;
        }
        res = res * res;
        n=n>>1;
    }
    return ans;
}

矩阵快速幂

基于整数快速幂幂的理念，我们可以照猫画虎写出矩阵快速幂的代码，为了简化代码风格，分为两个函数，mul实现正常两个矩阵的乘法，quickmatrix实现矩阵快速幂。

整数中的初始1，转为矩阵的单位矩阵。
整数中的幂N，保持不变
整数中的初始整数，转为初始矩阵

以下是代码：

vector<vector<int>> mul(vector<vector<int>> v1,vector<vector<int>> v2){
    int n = v1.size();
    vector<vector<int>> v(n,vector<int>(n,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                v[i][j] += v1[i][k] * v2[k][j];
            }
        }
    }
    return v;
}

vector<vector<int>> quickmatrix(int N,vector<vector<int>> matrix){
    int n = matrix.size();
    vector<vector<int>> ans(n,vector<int>(n,0));
    vector<vector<int>> tmp = matrix;

    for(int i=0;i<n;i++){
        ans[i][i] = 1;
    }

    while(N){
        if(N&1){
            ans = mul(ans,tmp);
        }
        tmp = mul(tmp,tmp);
        N = N>>1;
    }

    return ans;
}

快速求解斐波那契数列

矩阵快速幂的一个重要应用在于快速求解斐波那契数列，斐波那契数列为0，1，1，2，3，5，8，13，21，34……

按照计算规则 f(n) = f(n-1) + f(n-2)，其中f(0) = 0，f(1) = 1

我们将其转为矩阵形式为：
[ f ( n + 1 ) f ( n ) f ( n ) f ( n − 1 ) ] = [ 0 1 1 0 ] n \begin{gathered} \begin{bmatrix} f(n+1) & f(n) \\ f(n) & f(n-1) \end{bmatrix} &= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}^n \end{gathered} [f(n+1)f(n)​f(n)f(n−1)​]​=[01​10​]n​

然后调用函数

vector<vector<int>> v={{1,1},{1,0}};
vector<vector<int>> tmp = quickmatrix(9,v);
int res = tmp[0][1];