热身问题

首先考虑一个更简单的相关问题。
设 $G$ 为题目中表示城市与道路的图，$A$ 为其邻接矩阵。
假设我们不是要计算特殊旅行，而是要计算长度为 $k$ 且起点与终点相同的普通旅行的数量。

引理 1

对于任意 $k \ge 1$，$A^k$ 的第 $(i, j)$ 个元素 $(A^k)_{ij}$ 等于从 $i$ 出发、到 $j$ 结束的长度为 $k$ 的旅行的数量。

证明
当 $k = 1$ 时，由邻接矩阵的定义显然成立。
假设引理对 $k \ge 1$ 成立，考虑矩阵 $A^{k+1} = A^k A$。
由归纳假设，$(A^k)_{ij}$ 等于从 $i$ 到 $j$ 的长度为 $k$ 的旅行数。
那么从 $i$ 到 $j$ 的长度为 $k+1$ 的旅行数，等于从 $i$ 到某个与 $j$ 相邻的顶点 $l$ 的长度为 $k$ 的旅行数，这正是 $A^k A$ 所表示的，因此归纳成立。

因此，要计算长度为 $k$ 且起点与终点相同的旅行数，只需计算 $A^k$，然后将其对角线上元素求和（即矩阵的迹）。
为了高效计算，我们可以使用二进制快速幂技术。

设

$$I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix} $$

为单位矩阵，则：

$$A^k = \begin{cases} I, & \text{若 } k = 0, \\ \left(A^{k/2}\right)^2, & \text{若 } k > 0 \text{ 且 } k \text{ 为偶数}, \\ \left(A^{(k-1)/2}\right)^2 \cdot A, & \text{若 } k > 0 \text{ 且 } k \text{ 为奇数}. \end{cases} $$

由于每一步将指数减半，该过程需要 $O(\log k)$ 步。
每一步进行 1 或 2 次 $n \times n$ 矩阵乘法，朴素算法为 $O(n^3)$。
因此总时间复杂度为 $O(n^3 \log k)$。

---

完整问题

现在回到原问题：计算长度为 $k$、起点与终点相同且为特殊旅行的数量。

特殊旅行要求不连续两次使用同一条道路（即 $v_i \neq v_{i+2}$）。
我们无法直接用一个简单矩阵的幂表示它，但可以尝试用邻接矩阵描述。

设 $S(k)$ 为一个 $n \times n$ 矩阵，其 $(i, j)$ 元素等于从 $i$ 出发、到 $j$ 结束的长度为 $k$ 的特殊旅行的数量。
另外设 $D$ 为度数矩阵（对角矩阵），其中 $D_{ii}$ 等于顶点 $i$ 在图 $G$ 中的度数。

引理 2

以下等式成立：

1. $S(1) = A$
2. $S(2) = A^2 - D$
3. 对 $k > 2$，有$$S(k) = S(k-1) \cdot A - S(k-2) \cdot (D - I)$$

证明

• $k = 1$：长度为 1 的特殊旅行就是图中的边，显然成立。

• $k = 2$：$A^2$ 对应所有长度为 2 的旅行（允许连续用同一条边返回）。
  但特殊旅行不允许连续两次使用同一条边。长度为 2 的旅行中，连续用同一条边的情况正好是：从一个顶点 $v$ 出发，走一条邻边，再原路返回。
  这种旅行的数量正好是 $D_{vv}$，即 $v$ 的度数。因此去掉这些情况，得到 $S(2) = A^2 - D$。

• $k \ge 3$：
  考虑 $S(k-1) \cdot A$，它表示长度为 $k$ 的旅行，其中前 $k-1$ 步是特殊旅行，最后一步任意走邻边（可能连续使用上一步的边）。
  这正是我们想要的结果加上那些最后一步与倒数第二步使用了同一条边的非法情况。
  非法情况可以这样描述：先走一个长度为 $k-2$ 的特殊旅行到达某个顶点 $v$，然后走一条与 $v$ 相邻的边（但不能是刚刚到达 $v$ 的那条边，否则会在第 $k-2$ 步到 $k-1$ 步之间产生重复边吗？注意：这里“最后两步”指第 $k-1$ 步和第 $k$ 步），实际上需要更仔细分析。

  更准确的推导：
  $S(k-1)A$ 计数了所有长度为 $k$ 的路径，其中前 $k-1$ 步是特殊路径，第 $k$ 步任意走一条邻边。
  需要去除的情况是：第 $k$ 步走的路与第 $k-1$ 步走的路是同一条。
  这等价于：先走一个长度为 $k-2$ 的特殊路径到达某个顶点 $u$，然后从 $u$ 走到某个邻点 $v$（这条边记为 $e$），并且最后一步从 $v$ 走回 $u$ 沿同一条边 $e$。
  注意：从 $u$ 走到 $v$ 的这一步（第 $k-1$ 步）不能是前一步（第 $k-2$ 步）刚刚走过的边，但这是已经由 $S(k-2)$ 保证了（因为前 $k-2$ 步已经是特殊路径）。
  因此，对于每个长度为 $k-2$ 的特殊路径终点 $u$，它可以走任意一条邻边 $e$ 到 $v$（共 $\deg(u)$ 种选择），但其中有一条边可能是第 $k-2$ 步刚走过的吗？不是——因为第 $k-2$ 步是进入 $u$ 的最后一条边，这条边不能与第 $k-1$ 步的边相同，否则第 $k-2$ 步到第 $k-1$ 步会重复边。
  所以实际上，从 $u$ 出发可选的边是 $\deg(u) - 1$ 条（排除刚刚进入 $u$ 的那条边）。这正是 $(D - I)$ 对角元的意义。
  因此，非法情况的计数是 $S(k-2) \cdot (D - I)$。
  于是：

  $$S(k) = S(k-1)A - S(k-2)(D - I)$$

  证毕。

---

高效计算

现在我们有一个线性递推关系，可以用矩阵快速幂求解。

构造一个 $2n \times 2n$ 的分块矩阵：

$$L = \begin{bmatrix} A & I \\ -(D - I) & 0 \end{bmatrix} $$

注意 $L$ 是 $2n \times 2n$ 的矩阵。
考虑 $L$ 乘以一个列向量：

$$L \begin{bmatrix} X \\ Y \end{bmatrix} = \begin{bmatrix} A X + I Y \\ -(D - I) X + 0 \cdot Y \end{bmatrix} = \begin{bmatrix} A X + Y \\ -(D - I) X \end{bmatrix} $$

但我们更常用如下形式（题解原文略有不同，我们用标准形式）：

实际上原题解中给出的是：

$$L = \begin{bmatrix} A & -(D - I) \\ I & 0 \end{bmatrix} $$

这样：

$$L \begin{bmatrix} S(k) \\ S(k-1) \end{bmatrix} = \begin{bmatrix} A S(k) - (D - I) S(k-1) \\ S(k) \end{bmatrix} = \begin{bmatrix} S(k+1) \\ S(k) \end{bmatrix} $$

检查：
由递推 $S(k+1) = S(k)A - S(k-1)(D - I)$，正是上式第一个块。
第二个块为 $S(k)$，符合要求。

因此：

$$\begin{bmatrix} S(k) \\ S(k-1) \end{bmatrix} = L^{k-2} \begin{bmatrix} S(2) \\ S(1) \end{bmatrix}, \quad \text{对于 } k \ge 2 $$

其中 $S(1) = A$，$S(2) = A^2 - D$。

---

算法步骤

1. 读入 $n, m, k$，建图，计算邻接矩阵 $A$ 和度数矩阵 $D$。
2. 若 $k = 1$，答案为 $\operatorname{tr}(A) = 0$（因为无自环，对角线为 0）。
3. 若 $k = 2$，答案为 $\operatorname{tr}(A^2 - D) = \sum_i \left( (A^2)_{ii} - D_{ii} \right)$。
4. 若 $k \ge 3$：
   • 构造 $2n \times 2n$ 矩阵 $L = \begin{bmatrix} A & -(D-I) \\ I & 0 \end{bmatrix}$。
   • 计算 $L^{k-2}$（用矩阵快速幂，复杂度 $O((2n)^3 \log k) = O(n^3 \log k)$）。
   • 计算初始向量 $V = \begin{bmatrix} \operatorname{vec}(S(2)) \\ \operatorname{vec}(S(1)) \end{bmatrix}$（这里 $\operatorname{vec}$ 表示将 $n \times n$ 矩阵按行或列拉直为 $n^2$ 维向量？注意：实际上 $L$ 是 $2n \times 2n$ 操作在矩阵块上，不是拉直。我们保持 $S(1), S(2)$ 为 $n \times n$ 矩阵，直接进行分块矩阵乘法。）
   • 得到 $\begin{bmatrix} S(k) \\ S(k-1) \end{bmatrix}$。
   • 答案为 $\operatorname{tr}(S(k))$，即 $S(k)$ 对角线元素之和。
5. 所有运算模 $998244353$。

---

复杂度

• 时间：$O(n^3 \log k)$
• 空间：$O(n^2)$

---

总结

本题核心是将“禁止立即走回头路”的约束转化为线性递推，并用 $2n \times 2n$ 分块矩阵快速幂求解。
这结合了图论、矩阵快速幂和递推关系求解，是 $O(n^3 \log k)$ 的经典解法。