解决的问题
博客
洛谷专栏
矩阵乘法在图论中常用于(定长/限制类)路径统计和最短路问题。此类型题目的时间复杂度往往是 $O(n^3 \log k)$，故此类题目的点数不应过大。
一些代码技巧
struct Mat {
int n;
vector<VI> A;
vector<int>& operator [](int i) {return A[i];}
const vector<int>& operator [](int i) const { return A[i]; } //在矩阵乘法中放入这两个函数之后，便可以直接通过 `ans[1][5]` 访问数组元素，而不是 `ans.a[1][5]`。
Mat(int _n) : n(_n) {A.assign(n + 1, VI(n + 1, 0)); }
const Mat operator*(const Mat &B) const {
Mat C(n);
rep(i, 0, n) rep(j, 0, n)
rep(k, 0, n) (C[i][j] += (A[i][k] * B[k][j])
return C;
}
};
题
定长
模板题，按照题意在每个公交站之间连边即可，注意的是在到达终点之后不能从终点出来，终点的出度是 0。
定长
看到题目和数据范围后，不难想到矩阵快速幂求解 $k$ 步内到达某一结点的方案数这一类问题。
但是问题出现了，因为上述做法只能满足 “01矩阵”。
那我们就考虑将这个矩阵转化为 01矩阵不就完事了吗？
考虑给每个节点建立 8 个虚点，我们令 $(i,j)$ 表示距离节点 $i$，$j$ 个距离的点，$(i,0)$ 就代表节点 $i$，我们需要将 $(i, j)$ 和 $(i, j-1 )$ 通过一条有向边连接起来。
若此时有边连向这个节点，且距离为 $d$，那么我们就将它连接到 $(i, d – 1)$ 的节点处就可以了，此时这个邻接矩阵就转化为了 01 矩阵。
时间复杂度：$O((9n)^3 \log T)$
总结：如果一道题目是某类题型的变种，那我们可以将这道题想办法转化为我们熟悉的题型；
trick: 若路径长度 $\ge 1$ 可以建虚点，虚点之间的路径长度是 1，总长度依然等于原长。
限长
这道问题引入了停留和爆炸两个特殊的情况：
- 爆炸意味着不能再往后更新状态，故可以建立一个汇点，进了汇点就不能再出来，就满足了不能再往后更新状态
- 停留意味着花费一单位时间不动，建立自环就好，建立自环还可用于解决限长类问题。
以上两点也是矩阵乘法解决路径类问题常用的 trick。
定长最短路
定长最短路板子题，但是有一点值得一提，很容易搞混。关于 $\texttt{ans}$ 数组的初值问题。
在路径统计中 $\texttt{ans}[i][j]$ 的定义是从 $i – j$ 有多少种方案，很显然 $\texttt{ans}[i][i] = 0$，但是在最短路中，$\texttt{ans}[i][j]$ 的定义是从 $i-j$ 的最短路是多少，所以 $\texttt{ans}[i][i] = 0$，而其他的应当等于 $\infty$。
定长
首先看题目数据范围，$n \leq 100$ ，这种情况要么说明这道题的时间复杂度是比较高的，要么就和矩阵乘法脱不开关系。
阅读题目之后，我们发现可以应用 Floyd 最短路，也就是矩阵乘法的思想去描述每一轮每一个城市的魔法值。
故这道题应该先用邻接矩阵建图，矩阵快速幂求解。
结果就超时了，考虑通过倍增，二进制分解优化。
预处理时间复杂度 $O(n^3\log n)$ ，单次询问时间复杂度 $O(n^2\log n)$ 。
总结：对于数据范围比较小的图论题要联想到邻接矩阵，对于经常会用到的数据不必重复计算，考虑记录下来优化程序的运行效率。
倍增适合于各种各样的优化，非常实用
快速幂也算是二进制拆分，二进制拆分可以用于快速幂的预处理，还能用于喝果汁那道题
像这种和步数有关的题，应该联想到邻接矩阵，邻接矩阵虽然不常用，但是依然很重要。
trick: 若需要执行多次快速幂，考虑提前预处理 base。
限长类问题。
朴素的 DP 很好想，不再赘述且貌似对思考正解没有帮助。
$T$ 很大，要么二分要么倍增要么数学要么矩阵。由于配合图论，故考虑矩阵。先从简单开始考虑，若此题不存在材料的限制，且是定长类问题，那么这就是一个板的矩阵乘法。
上文的两个 trick 此时发挥了他的作用，由于要求的时间是 $\le T$，且最终的状态只能在出发点，故在点 1 建立自环，但是这真的对吗？
根据题目描述可知，若回到家了就不能再买东西，故不能在 1 建立自环，而是应当连接一条 1 到汇点0 的有向边，接着在汇点连自环，这样就保证了真真的结束。（说白了就是可乐那道题的爆炸，提前结束的意思）。
由于去商店需要两条边，可以考虑建立虚点代表商店。
到此为止问题已经解决了一大半，接着我们就需要考虑如何处理原料的问题。
注意到如果问题有以下特征：
- 正着求你根本不知道该如何实现，若干个条件去掉之后（不满足要求）的处理并不难。
- 需要同时满足若干个条件的计数问题。
- 如果考虑暴力转移，时间复杂度是条件数的高次。
就可以考虑容斥，其本质就是为了不重复计算，把多个条件的互相影响，化为了每个条件执行一次，成了线性做法。
容斥原理和倍增一样都是超级常见的套路，需要重点掌握。