【模板】矩阵快速幂

矩阵快速幂

前置芝士

矩阵乘法

• 当矩阵$A$的列数与矩阵$B$的行数相等时，矩阵$A$与矩阵$B$可进行相乘

• 如矩阵$A$为$m\times n$的矩阵，矩阵$B$为$n \times p$的矩阵，他们的乘积$C$是一个$m \times p$的矩阵

• $C$的第$i$行$j$列的元素为

  $$c_{i,j}=\sum\limits^n_{r=1}a_{i,r}b_{r,j}$$

• 举例

  • $\begin{bmatrix}a\c\end{bmatrix} \times \begin{bmatrix}b&d\end{bmatrix}=\begin{bmatrix}a\times b&a \times d\c \times b&c\times d\end{bmatrix}$

  • 

    懒得打了直接引的百度百科图片

• 方阵：行数等于列数的矩阵

• 单位矩阵：左上角到右下角这条对角线上全为1、其余全为0的方阵（相当于乘法中的1）

• 矩阵乘法有结合律、分配律，没有交换律

快速幂

见快速幂(主要用带取模的快速幂)

矩阵快速幂

• 顾名思义，其实就是矩阵乘法+快速幂

• typedef long long ll;
  const int maxN = 110;
  const int MOD = (1e9+7);
  int n;
  
  struct Matrix{
      ll d[maxN][maxN];
      Matrix(){memset(d,0,sizeof(d));}
      void init(){
          for(int i = 1;i<=n;i++){
              d[i][i] = 1;
          }
      }
      friend Matrix operator * (Matrix A,Matrix B){
          Matrix C;
          for(int i = 1;i<=n;i++){
              for(int j = 1;j<=n;j++){
                  for(int k = 1;k<=n;k++){
                      C.d[i][k] += (A.d[i][j] * B.d[j][k]) % MOD;
                      C.d[i][k] %= MOD;
                  }
              }
          }
          return C;
      }
  };
  
  Matrix quickPow(Matrix A,ll b){
      Matrix B;
      B.init();
      while(b){
          if(b&1) B = B * A;
          A = A * A;
          b /= 2;
      }
      return B;
  }
  

应用

1. 超大数的递推，如P1962斐波那契数列

   因为我们知道，

   $f(n)=f(n-1)+f(n-2)$

   $f(n-1)=f(n-1)$

   即

   $\begin{align}\begin{cases}f(n)&=1\times f(n-1)+1\times f(n-2)\f(n-1)&=1\times f(n-1)+0\times f(n-2)\end{cases}\end{align}$

   因此我们得到了

   $\begin{bmatrix}f(n)\f(n-1)\end{bmatrix}=\begin{bmatrix}1&1\1&0\end{bmatrix}\times \begin{bmatrix}f(n-1)\f(n-2)\end{bmatrix}$

   因为矩阵乘法具有结合律，所以斐波那契数列的第n项为

   $\begin{bmatrix}f(n)\f(n-1)\end{bmatrix}=\begin{bmatrix}1&1\1&0\end{bmatrix}^{n-2}\times \begin{bmatrix}1\1\end{bmatrix}$

   算就完了

   矩阵的katex打起来太麻烦了( ‵o′)