文章目录

BZOJ 4887 [TJOI 2017] 可乐 做题笔记

发布于

题意

加里敦星球的人们特别喜欢喝可乐。因而,他们的敌对星球研发出了一个可乐机器人,并且放在了加里敦星球的 $1$ 号城市上。这个可乐机器人有三种行为:停在原地、去下一个相邻的城市。自爆。它每一秒都会随机触发一种行为。现在给出加里敦星球城市图,在第 $0$ 秒时可乐机器人在 $1$ 号城市,问经过了 $t$ 秒,可乐机器人的行为方案数是多少?

一共有 $n$ 个点,$m$ 条边。

$1 \leq n \leq 30, 1 \leq m \leq 100, 1 \leq t \leq 10^6$

题解

邻接矩阵自乘即可。
停在原地表示为自环。
自爆表示为走向哨兵节点。
矩阵的 $t$ 次幂的第一行的和即为答案。
时间复杂度 $\Theta \left(n^3 \log t\right)$


暂无评论

发表评论