1机房今天晚上不知道为啥把洛谷也关了，AC自动机没题做了，教练您做的好啊
那么就冲一个矩阵乘法和快速幂吧，开了提高OJ之后还有几道需要矩阵乘法的AC自动机没写，后面再冲一下状压虽然已经冲过了
矩阵
矩阵思想来源于线性方程组
如方程组
\[\begin{equation} \begin{cases} 7x_1+8x_2+9x_3=13 \\ 4x_1+5x_2+6x_3=12 \\ x_1+2x_2+3x_3=11 \end{cases} \end{equation} \]写成矩阵乘法
\[\begin{equation} \begin{pmatrix} 7 & 8 & 9 \\ 4 & 5 & 6 \\ 1 & 2 & 3 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}=\begin{pmatrix} 13 \\ 12 \\ 11 \end{pmatrix} \end{equation} \]简记
\[Ax=b \]即未知数列向量 \(x\)，左乘矩阵 \(A\)，得到列向量 \(b\)
矩阵乘法
矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义
\(A\) 为 \(p \times m\) 的矩阵， \(B\) 为 \(m \times q\) 的矩阵，设矩阵 \(C\) 为矩阵 \(A\) 与 \(B\) 的乘积，
那么对于\(C_{i,j}\)可以表示为
\[C_{i,j}=\sum _{k=1} ^ {m} A_{i,k}\times B_{k,j} \]\(C_{i,j}\) 就是由矩阵 \(A\) 第 \(i\) 行 \(m\) 个数与矩阵 \(B\) 第 \(j\) 列 \(m\) 个数分别 相乘再相加 得到的
矩阵乘法满足结合律却不满足相对律
也就是说
\[A\times B \times C=A \times (B \times C) \neq A \times C \times B \]这是非常显而易见的
利用结合律，矩阵乘法可以利用 快速幂 的思想来优化，也就是矩阵快速幂
没时间了后面的过两天再写
标签：begin,end,矩阵,times,pmatrix,快速,乘法 From： https://www.cnblogs.com/LuoTianYi66ccff/p/17924867.html