矩阵快速幂

## 矩阵乘法 对于$(n,m)$的矩阵A和$(m,k)$的矩阵B,$A*B=C$，C为n行k列，$C_{i,j}=\sum_{i=1}^m A_{i,k}*B_{k,j}$ ## 矩阵快速幂 矩阵快速幂就是求$A^k$。 显然$A^k=\underbrace{A*A*A*A*A*...*A}_k$ 首先矩阵乘法满足结合律，所以我们可以用类似快速幂的做法来求 然后矩阵乘法的时间复杂度是$O(nmk)$，所以一般而言矩阵边长$\leq 100$ ## 应用 1. 线性递推加速 对于形如$f_i=f_{i-1}+f_{i-2}$，$f_i=af_{i-1}+c$的式子构造矩阵 $[f_n \space f_{n-1}]=\begin{bmatrix}1&1\\1&0\end{bmatrix}[f_{n-1}\space f_{n-2}]$ $[f_n \space f_{n-1}]=\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-2}[f_2 \space f_1]$ ________________________________ $\begin{bmatrix} f_n\\c \end{bmatrix}=\begin{bmatrix}a&1\\0&1\end{bmatrix} \begin{bmatrix} f_{n-1} \\ c\end{bmatrix}$ $\begin{bmatrix} f_n\\c \end{bmatrix}=\begin{bmatrix}a&1\\0&1\end{bmatrix}^{n-2} \begin{bmatrix} f_0 \\ c\end{bmatrix}$ 2. 转移相同的分层图dp 暴力 ```cpp f[1][0]=1; for(int j=1; j<=t; j++){ for(int x=1; x<=n; x++){ for(int i=head[x]; i; i=Next[i]){ int y=ver[i]; f[y][j]=(f[y][j]+f[x][j-1])%mod; } } } ``` 显然$f_{x,j}=\sum_{G_{x,y}=1} f_{y,j}$ 所以我们在转移的时候让转移矩阵里的$(x,y)$为1，其他为0，然后跑矩阵快速幂 $f_n=G*f_{n-1}$ $f_n=G^n*f_0$