P4159 [SCOI2009] 迷路 & 矩阵优化动态规划

· · 个人记录

我们先考虑怎么求解边权都为一的情况。题目中给我们的是一个邻接矩阵。我们设 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, t)$，展开一下就是 $M^t$。由于 $M$ 是方阵，我们可以用矩阵快速幂。 然后我们来考虑本题：虽然有了边权，但实际上边权最大也只是 $9$，那么我们可以这么考虑：建一些虚点设为 $\sigma_{ik}$，这些虚点之间的边权都是一，然后就转化成了上一个问题。 btw，发现矩阵乘法用循环展开可以卡两倍常