解决的问题

博客

洛谷专栏

矩阵乘法在图论中常用于 (定长 / 限制类) 路径统计和最短路问题。此类型题目的时间复杂度往往是 $O (n^3 \log k)$，故此类题目的点数不应过大。

• OI-wiki

一些代码技巧

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;
    }
};

题

P2233 [HNOI2002] 公交车路线

定长

模板题，按照题意在每个公交站之间连边即可，注意的是在到达终点之后不能从终点出来，终点的出度是 0。

P4159 [SCOI2009] 迷路

定长

看到题目和数据范围后，不难想到矩阵快速幂求解 $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，总长度依然等于原长。

P3758 [TJOI2017] 可乐

限长

这道问题引入了停留和爆炸两个特殊的情况：

• 爆炸意味着不能再往后更新状态，故可以建立一个汇点，进了汇点就不能再出来，就满足了不能再往后更新状态
• 停留意味着花费一单位时间不动，建立自环就好，建立自环还可用于解决限长类问题。

以上两点也是矩阵乘法解决路径类问题常用的 trick。

P2886 [USACO07NOV] Cow Relays G

定长最短路

定长最短路板子题，但是有一点值得一提，很容易搞混。关于 $\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$。

P6569 [NOI Online #3 提高组] 魔法值

定长

首先看题目数据范围，$n \leq 100$ ，这种情况要么说明这道题的时间复杂度是比较高的，要么就和矩阵乘法脱不开关系。

阅读题目之后，我们发现可以应用 Floyd 最短路，也就是矩阵乘法的思想去描述每一轮每一个城市的魔法值。

故这道题应该先用邻接矩阵建图，矩阵快速幂求解。

结果就超时了，考虑通过倍增，二进制分解优化。

预处理时间复杂度 $O (n^3\log n)$ ，单次询问时间复杂度 $O (n^2\log n)$ 。

总结：对于数据范围比较小的图论题要联想到邻接矩阵，对于经常会用到的数据不必重复计算，考虑记录下来优化程序的运行效率。

倍增适合于各种各样的优化，非常实用
快速幂也算是二进制拆分，二进制拆分可以用于快速幂的预处理，还能用于喝果汁那道题
像这种和步数有关的题，应该联想到邻接矩阵，邻接矩阵虽然不常用，但是依然很重要。

trick: 若需要执行多次快速幂，考虑提前预处理 base。

P5188 [COCI2009-2010#4] PALACINKE

限长类问题。

朴素的 DP 很好想，不再赘述且貌似对思考正解没有帮助。

$T$ 很大，要么二分要么倍增要么数学要么矩阵。由于配合图论，故考虑矩阵。先从简单开始考虑，若此题不存在材料的限制，且是定长类问题，那么这就是一个板的矩阵乘法。

上文的两个 trick 此时发挥了他的作用，由于要求的时间是 $\le T$，且最终的状态只能在出发点，故在点 1 建立自环，但是这真的对吗？

根据题目描述可知，若回到家了就不能再买东西，故不能在 1 建立自环，而是应当连接一条 1 到汇点 0 的有向边，接着在汇点连自环，这样就保证了真真的结束。（说白了就是可乐那道题的爆炸，提前结束的意思）。

由于去商店需要两条边，可以考虑建立虚点代表商店。

到此为止问题已经解决了一大半，接着我们就需要考虑如何处理原料的问题。

注意到如果问题有以下特征：

1. 正着求你根本不知道该如何实现，若干个条件去掉之后（不满足要求）的处理并不难。
2. 需要同时满足若干个条件的计数问题。
3. 如果考虑暴力转移，时间复杂度是条件数的高次。

就可以考虑容斥，其本质就是为了不重复计算，把多个条件的互相影响，化为了每个条件执行一次，成了线性做法。

容斥原理和倍增一样都是超级常见的套路，需要重点掌握。