终于学习了矩阵快速幂，原来矩阵构造是easy
矩阵乘法
内容
两个矩阵相乘需要满足一个矩阵的列和第二个矩阵的行相同，并且不符合交换律结合律，若第一个矩阵为 $n·k$，第二个矩阵为 $k·m$，这两个矩阵相乘得到的矩阵规模为 $n·m$。
应用
matrix67: 十个利用矩阵乘法解决的经典题目
VOJ1067
给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
(n<=100)
题解
- 将有向图转化为邻接矩阵A
- 考虑邻接矩阵每个点$A_{ij}$的含义为：$i->j$存在长度为 $1$ 的边
- 令$C=A×A$，则$C_{ij}$的含义为：$i->j$路径长度为2的方案数
- 所以$A^k_{ab}$即为所求
- 矩阵快速幂求$A^k$
矩阵快速幂
mama我终于学会了构造矩阵
其实这个就是一个很简单的东西。