矩阵快速幂

定义

---

矩阵快速幂

矩阵快速幂应用了和快速幂相同的思想，将指数n进行二进制分解进行高效计算。

实现

---

int n, MOD;  
  
struct matrix  
{  
    int A[n + 1][n + 1];  
};  
  
matrix multiply(matrix& A, matrix& B, int n, int m, int p)  
{  
    matrix C;  
    for (int i = 1; i <= n; i++) // A的行，C的行  
       for (int k = 1; k <= p; k++) // A的列，B的行  
          for (int j = 1; j <= m; j++) // B的列，C的列  
             C.A[i][j] += A.A[i][k] * B.A[k][j];    
		     // C.A[i][j] = (C.A[i][j] + A.A[i][k] * B.A[k][j]) % MOD; // 取模
    return C;  
}  
  
matrix quick_pow(matrix& A, int exp)  
{  
    matrix res;  
    for (int i = 1; i <= n; i++)  
       res.A[i][i] = 1; // 初始化为单位矩阵  
    while (exp)  
    {  
       if (exp & 1)  
          res = multiply(res, A, n, n, n);  
       A = multiply(A, A, n, n, n);  
       exp >>= 1;  
    }  
    return res;  
}