自动搬运

查看原文

来自洛谷，原作者为

	xxr___ CSP-S2025 rp++!

搬运于2025-08-24 23:11:00，当前版本为作者最后更新于2025-04-02 07:35:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先看到可达性问题，而且 $N$ 的范围不大，并且 $k$ 的值很大，就很难不想到矩阵快速幂。

但是这个题和普通的题不同，这个题的边权 $w\leq 10$ 不能用朴素版本来做，但是可以考虑把每个点拆成 $10$ 个点使得他们变成一条链的形态，具体建边的方式如下：

1. 把每个点拆成 $10$ 个点，我们称他叫做点 $i$ 的附属点。第 $i$ 个点的第 $j$ 个附属点的编号为 $i+(j-1)\times n$ 这样编号的好处就是不会重复，避免边和边之间的交叉问题。
2. 连边的时候，首先第 $i$ 个点的第 $j$ 个附属点向第 $i$ 个点的第 $j+1$ 个附属点连边，可以保证 $i$ 的附属点是一条链的结构。
3. 连那 $M$ 条边的时候，设边权为 $w$ 则把 $u$ 的第 $w$ 个附属点向 $v$ 连边。

这样我们就构造好了初始矩阵，接下来考虑矩阵快速幂的时候如何更新矩阵。

由于我们每个点增加了 $10$ 个附属点，所以现在一共有 $10\times n$ 个节点，也就是 $1000$ 级别，如果直接上矩阵快速幂并且使用朴素版更新的话是 $O(n^3\log k)$ 的，这里 $n\leq 1000$ 所以无法接受，我们发现在更新的时候实际上是类似于一个传递闭包的形式的，并且 $j$ 的那一维是没有用的所以可以使用 bitset 优化它，这样时间复杂度就变成了 $O(\frac{n^3}{w} \log k)$ 可以通过。

代码