Fast Power

  • 乘法快速幂

  • 矩阵乘法、矩阵快速幂

    • 固定关系的1维k阶递推表达式，用矩阵快速幂求解时间复杂度 ）
    • 固定关系的k维1阶递推表达式，用矩阵快速幂求解时间复杂度

乘法快速幂

  • 乘法快速幂是计算 的一种高效算法，时间复杂度为 。

  • 其基本思想是将指数 转化为二进制形式，然后利用二进制的性质进行快速计算。

int pow(int a, int b,int mod){
    int ans=1;
    while(b){
    	if(b&1) ans=(ans*a)%mod;
    	 a = a*a%p;
    	 b>>=1;
    }
    return ans;
}

矩阵快速幂

矩阵乘法:

vector<vector<int>> matrixMultiply(const vector<vector<int>>& A, const vector<vector<int>>& B) {
    int rowsA = A.size();
    int colsA = A[0].size();
    int colsB = B[0].size();
    vector<vector<int>> C(rowsA, vector<int>(colsB, 0));
    for (int i = 0; i < rowsA; ++i) {
        for (int j = 0; j < colsB; ++j) {
            for (int k = 0; k < colsA; ++k) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

矩阵快速幂:

  • 矩阵快速幂是计算 的一种高效算法，时间复杂度为 。 是一个的方阵。
  • 其基本思想与乘法快速幂相同，将指数 转化为二进制形式，然后利用二进制的性质进行快速计算。
vector<vector<int>> matrixPow(vector<vector<int>>& M, int n ){
    int matrixSize = M.size();
    vector<vector<int>> ans(matrixSize, vector<int>(matrixSize, 0));
    for(int i=0;i<matrixSize;i++){
        ans[i][i]=1;
    }
    for(;n!=0;n>>=1){
        if(n&1) ans = matrixMultiply(ans,M);
        M = matrixMultiply(M,M);
    }
    return ans;
}
Table Of Contents
Fast Power
乘法快速幂
矩阵快速幂