算法总结—矩阵加速

矩阵

矩阵类似于二维数组：
\(A=\begin{bmatrix}a&b\\c&d\end{bmatrix}\)
矩阵的用途

• 解方程。
  
• 加速线性 DP。
  
• 加速 Floyd。
  

常数乘法

\(Ak=\begin{bmatrix}ak&bk\\ck&dk\end{bmatrix}\)
矩阵乘法

若 \(A=\begin{bmatrix}a&b\\c&d\end{bmatrix}\)，\(B=\begin{bmatrix}x&y&z\\u&v&w\end{bmatrix}\)
则 \(C=A\times B=\begin{bmatrix}ax+bu&ay+bv&az+bw\\cx+du&cy+dv&cz+dw\end{bmatrix}\)
也就是 \(C_{i,j}=\sum_{i=1}^{A\tt{的列数}} A_{i,k}B_{k,j}\)，所以在矩阵乘法中，\(A\) 的列数要等与 \(B\) 的行数。
单位矩阵

单位矩阵就是形如 \(\begin{bmatrix}1&0&\cdots&0\\0&1&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&1\end{bmatrix}\) 的矩阵，任何矩阵乘单位矩阵都等于自己，就相当于整数中的 \(1\)。
矩阵快速幂

矩阵快速幂与整数快速幂类似，唯一的不同是需要重载一下矩阵的乘法。
【模板】矩阵快速幂

快速幂
代码

[code]#include#define int long longusing namespace std;const int mod=1e9+7;int n,p;struct matrix{        int n,m;        int a[105][105];        matrix():n(0),m(0){                memset(a,0,sizeof(a));                return;        }        matrix(int x,int y):n(x),m(y){                memset(a,0,sizeof(a));                return;        }        matrix operator*(const matrix&b){                matrix c(n,b.m);                for(int i=1;ip;    matrix A(n,n);        for(int i=1;iA.a[j];                }        }        matrix ans=qpow(A,p);        for(int i=1;i>y>>n>>mod;    if(n==1){        coutg;        matrix A(1,2);        A.a[1][1]=x0,A.a[1][2]=c;        matrix B(2,2);        B.a[1][1]=a,B.a[1][2]=0;        B.a[2][1]=1,B.a[2][2]=1;        matrix C=qpow(B,n);        A=A*C;        cout