给出一个 $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)$$
提交评论