题目分析

本题要求计算从起点 $(A)$ 到终点 $(B)$、长度为 $(t)$ 的路径数量，且路径需满足“不能立刻沿刚刚走过的路返回”的约束（即连续两步不能是相反方向的同一条边）。每条边的长度为 $(1)$，最终结果需对 $(45989)$ 取模。

由于 $(t)$ 最大可达 $(2^{30})$，直接通过暴力枚举或普通动态规划（DP）会因时间复杂度过高而不可行，需借助高效的矩阵快速幂技术优化计算。

算法思路

核心是通过状态建模和矩阵快速幂解决带约束的长路径计数问题，具体步骤如下：

1. 状态定义：
   为避免“立刻返回”的约束，将状态设计为 $((u, v))$，表示“当前位于节点 $(v)$，上一步来自节点 $(u)$”。这样，下一步只能从 $(v)$ 走向除 $(u)$ 之外的相邻节点，自然满足约束条件。

2. 转移矩阵构建：
   构建转移矩阵 $(M)$，其中 $(M[(u, v)][(v, w)] = 1)$ 当且仅当存在从 $(v)$ 到 $(w)$ 的边且 $(w \neq u)$（即从状态 $((u, v))$ 可转移到 $((v, w))$）。矩阵的乘法对应状态的转移叠加，可用于计算多步后的路径数。

3. 矩阵快速幂加速：
   路径长度为 $(t)$ 的计数等价于转移矩阵的 $(t)$ 次幂与初始状态向量的乘积。利用矩阵快速幂（时间复杂度 $(O(\log t))$），可高效计算指数级步数的转移结果，避免超时。

4. 初始状态与结果提取：
   初始状态为从起点 $(A)$ 出发的第一步：所有以 $(A)$ 为起点的边 $((A, v))$ 对应状态 $((A, v))$，初始计数为 $(1)$。最终结果为所有状态 $((u, B))$ 在 $(t)$ 步后的计数总和。

复杂度分析

• 时间复杂度：设节点数为 $(N)$，则状态数为 $(O(N^2))$，矩阵乘法复杂度为 $(O((N^2)^3) = O(N^6))$，结合快速幂的 $(\log t)$ 次迭代，总复杂度为 $(O(N^6 \log t))$。由于 $(N \leq 50)$，该复杂度可满足 $(t \leq 2^{30})$ 的数据范围。
• 空间复杂度：$(O(N^4))$，主要用于存储转移矩阵和中间计算结果。

算法标签

• 矩阵快速幂
• 图论
• 路径计数
• 动态规划（DP）
• 状态转移