矩阵加速图上问题

概述

图上游走问题。

邻接矩阵的 $k$ 次幂为图上通过 $k$ 条边到达的方案数。

矩阵乘向量的时间复杂度为 $O(n^2)$。对于求 $\vec vA^k$，可以预处理

$$A^1,A^2,...,A^{B} \\ A^{B},A^{B^2},...,A^{B^{\log_B k}}$$

时间复杂度 $O(n^3(B+\log_B k))-O(n^2\log_B k)$。

参考

矩阵加速图上问题