可乐（数据加强版）题解

思路推导

机器人尚未自爆时，每秒可以停留、沿一条相邻道路移动，或立刻自爆。一个合法方案要么连续执行恰好 $t$ 次停留或移动，要么先执行 $k$ 次停留或移动，再在第 $k+1$ 次行为自爆，其中 $0\le k<t$。

为了统一表示这些长度不同的方案，增设一个吸收态 $D$。每座城市都有一条到 $D$ 的“自爆”转移，而 $D$ 只有一条到自身的转移。提前自爆后，方案沿唯一的自环补齐剩余秒数。由于补齐没有任何选择，同一方案不会被重复计算。

做法

建立 $N+1$ 阶转移矩阵 $T$，前 $N$ 个状态对应城市，最后一个状态对应 $D$：

• 对每座城市 $i$，令 $T_{i,i}$ 加一，表示停留；
• 对每条无向道路 $u-v$，令 $T_{u,v}$ 和 $T_{v,u}$ 各加一；
• 对每座城市 $i$，令 $T_{i,D}$ 加一，表示自爆；
• 令 $T_{D,D}=1$，表示已经自爆的方案唯一地补齐后续时间。

初始行向量只有城市 $1$ 的分量为 $1$。用二进制快速幂计算初始向量乘 $T^t$，再把结果向量的全部 $N+1$ 个分量相加并对 $2017$ 取模。

正确性证明

任意未自爆方案唯一对应一条始终位于城市状态、长度为 $t$ 的增广路径。任意在第 $k+1$ 次行为自爆的方案，唯一对应前 $k$ 次城市转移、一次进入 $D$ 的转移，以及 $t-k-1$ 次 $D$ 自环。反过来，删除进入 $D$ 后的补齐自环，也能唯一恢复原方案。因此合法方案与增广图中从城市 $1$ 出发的长度 $t$ 路径构成双射。

矩阵乘法按中间状态分类统计路径，故初始向量乘 $T^t$ 的每个分量恰好是到达对应状态的方案数。对全部分量求和即为题目所求。

部分分算法

若图是 $d$ 正则图，每一步停留或移动共有恒定的 $d+1$ 种选择，所以长度 $k$ 的未爆炸方案数为 $(d+1)^k$，总答案为 $\sum_{k=0}^{t}(d+1)^k$。用二进制拼接同时维护幂与前缀和，可在 $O(N+M+\log t)$ 时间内完成。

当 $N,M\le30$ 且 $t\le1000$ 时，可以按秒维护各城市中尚未自爆的方案数以及已经自爆的方案数，复杂度为 $O(t(N+M))$。

复杂度分析

满分算法的时间复杂度为 $O((N+1)^3\log t)$，空间复杂度为 $O((N+1)^2)$。所有乘加都使用 64 位有符号整数并及时对 $2017$ 取模。$t=0$ 时矩阵幂为单位矩阵，答案为 $1$。