文章目录

洛谷 P4159 SCOI2009 迷路 做题笔记

发布于

题意

给出一个 $n$ 个点的有向图,每条边的权值都在 $\left[1, 9\right]$ 之间。给出 $t$ ,求从 $1$ 到 $n$,经过路径边权和恰好为 $t$ 的方案数模 $2009$。

$1 \leq n \leq 10, 1 \leq t \leq 10^9$

题解

将 $1$ 个点拆成 $9$ 个点连成链,每次将出点对应边权的点连到入点上。这样点数就是 $9n$ 了。然后就是裸的矩乘。

$$\mathcal O\left(\left(9n\right)^3\right)$$


暂无评论

发表评论