矩阵乘法（个人笔记）

# 矩阵乘法 --------- 矩阵乘法就是$2$个矩阵相乘。 如果 矩阵$A$是$n$行$p$列 ，矩阵$B$是$p$行$m$列 ，$C=A*B $，那么矩阵$C$是$n$行$m$列 其中，矩阵$C$的$i$行$j$列是这样算的↓，（代码更能解释清楚） ```cpp void calc(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=p;k++) C[i][j]+=A[i][k]*B[k][j]; } ``` 上面的代码可以看出，矩阵乘法是$O(n^3)$的 -------------- 矩阵乘法**满足结合律，分配律**，**不满足交换律**。 利用结合律和分配律，我们可以利用矩阵乘法解决很多问题。 例如 ： **结合律 -> 矩阵快速幂** 例子：求第$n$项的斐波拉契数列，对$1e9+7$取模。 $ \begin{bmatrix} 1&1\\1&0\end{bmatrix}\times\begin{bmatrix} f(n-1)\\f(n-2)\end{bmatrix} =\begin{bmatrix} f(n-1)+f(n-2)\\f(n-1)\end{bmatrix}= \begin{bmatrix} f(n)\\f(n-1)\end{bmatrix}$ 所以对于求$f(n)$我们可以这么写: $\begin{bmatrix} f(n)\\f(n-1)\end{bmatrix} = {\begin{bmatrix} 1&1\\0&1\end{bmatrix}}^{n-2} \times \begin{bmatrix} f(2)\\f(1)\end{bmatrix}$ ${\begin{bmatrix} 1&1\\0&1\end{bmatrix}}^{n-2}$显然用矩阵快速幂求一下就行了。 -------- 矩阵快速幂模板： ```cpp matrix qpow(matrix p,int q){ matrix res; for(int i=1;i<=n;i++) res.a[i][i]=1; while(q){ if(q&1)res=res*p; p=p*p; q>>=1; } return res; } ``` >补充一下为什么初始矩阵是一个由左上角到右下角为$1$的矩阵， >因为这个矩阵是单位矩阵，相当于$1$， >矩阵$A$ * 单位矩阵 = 矩阵$A$ --------- 矩阵$ans$=$pow($矩阵$tmp,K) \times$矩阵$begin$； 若状态$i$能转移到状态$j$，$tmp.a[j][i]++;$ ------- ### 特殊的矩阵：相伴矩阵。 相伴矩阵也是循环矩阵，如果已知第一行，那么$n$行的信息也知道了（因为信息一样，只是位置变了），遇到这种矩阵要注意，这种矩阵可以使$O(n^3)$的矩阵乘法变成$O(n^2)$（因为少算了$n-1$行） 例题：[专题G](https://cn.vjudge.net/contest/276406#problem/G) --------- ### 多次方相加 我们需要求下面一个式子： $$ x^1+x^2+x^3+x^4+x^5+x^6 $$ 利用二分的思想我们可以得到： $$ x^1+x^2+x^3+x^3*(x^1+x^2+x^3)$$ 即 $$ (x^1+x^2+x^3)*(1+x^3) $$ 递归处理即可。 同样，因为**矩阵乘法满足分配律的性质**，所以同样可以这么写。 >注意，如果 $(1+x^3)$ 部分用了矩阵快速幂，那么复杂度就会达到$O(log^2n)$。 >有些题目不能这么写，所以不能快速幂，需要预处理（略）。复杂度降为$O(logn)$ 例题：[专题L](https://cn.vjudge.net/contest/276406#problem/L) ---------- 矩阵乘法适用于状态转移多次，尤其是计数问题的时候，只要状态定义的好，那么套上矩阵乘法优化，就可以轻松解决了。 例题：[专题M](https://cn.vjudge.net/contest/276406#problem/M) -------- 矩阵乘法还可以适用于多米诺骨牌这类转移状态问题，只要把边连上套个矩阵快速幂就行了 例题：[专题N](https://cn.vjudge.net/contest/276406#problem/N)