本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-05 19:55:53

我们先考虑怎么求解边权都为一的情况。题目中给我们的是一个邻接矩阵。我们设 $f(i, j)$ 表示从点 $1$ 走到点 $i$，走 $j$ 步的方案数量，那么显然有：

$$f(i, j) = \sum\limits_{k=0}^n M_{ki} \times f(k, j - 1)$$

换一个角度，如果将 $f(i,j)$ 看作是矩阵（向量） $f$，那么有：

$$f_{ij} =\sum\limits_{k=0}^n M_{ki} \times f_{kj-1}$$

我们滥用一下符号，于是后面实际上是个矩阵乘法 $f_{j-1}\times M$。我们就有：

$f(i, j) = f(i,j-1)\times M$。

我们要求的是 $f(i, t)$，展开一下就是 $M^t$。由于 $M$ 是方阵，我们可以用矩阵快速幂。

然后我们来考虑本题：虽然有了边权，但实际上边权最大也只是 $9$，那么我们可以这么考虑：建一些虚点设为 $\sigma_{ik}$，这些虚点之间的边权都是一，然后就转化成了上一个问题。

btw，发现矩阵乘法用循环展开可以卡两倍常