原题链接：https://www.luogu.com.cn/problem/P2151
题意解读：求A到B点经过t条边，一共有多少条路径。
解题思路：
根据https://www.cnblogs.com/hackerchef/p/18934500
定理1的描述，可知，设g[i][j]=1表示从i点到j点有路径，求gt可以得到A到B经过t条边的路径数。
但是此题有一个限制，不能立马走回头路！
因此，可以应用一个常用技巧：将点之间有路径换成边之间有路径。
也就是，将无向边拆成两条有向边，边u->v与边v->t是可以到达的，不走回头路意味着u->v不能到v->u。
基于边来建立矩阵g，要计算经过t条边，由于初始已经有一条边，只需要求ans=gt-1即可。
答案是枚举所有的ans[A为起点的边][B为终点的边]求和。
100分代码：（代码由claude code生成）
// 洛谷 P2151 [SDOI2009] HH去散步
// 问题描述：给定一个无向图，求从点A到点B恰好经过t条边的路径数，且要求路径中不能连续走同一条无向边的两个方向（即不能立刻走回头路）。
// 算法思路：将无向边拆分为两条有向边，以有向边为状态构建转移矩阵，使用矩阵快速幂计算走t-1步后的方案数。
// 状态定义：矩阵M[i][j]表示从有向边i走到有向边j（即i的终点是j的起点，且i和j不是同一条无向边的反向）的方案数（0或1）。
// 答案计算：枚举从A出发的有向边i和到达B的有向边j，累加M^(t-1)[i][j]。
// 时间复杂度：O((2m)^3 * log t)，其中m为边数，使用矩阵乘法优化后实际运行更快。#include <bits/stdc++.h>
using namespace std;const int MOD = 45989; // 题目要求的模数
const int MAXM = 130; // 最大有向边数：2*m <= 120，预留一些空间// 矩阵类，用于表示有向边之间的转移关系
struct Matrix {int a[MAXM][MAXM]; // 矩阵元素，a[i][j]表示从边i到边j是否存在转移（0或1）int n; // 矩阵大小（有向边的数量）// 构造函数，初始化大小为size的零矩阵Matrix(int size = 0) : n(size) {memset(a, 0, sizeof(a));}// 矩阵乘法，重载*运算符// 使用优化：当a[i][k]不为0时才进行内层循环，减少不必要的计算Matrix operator * (const Matrix &b) const {Matrix res(n);for (int i = 0; i < n; i++)for (int k = 0; k < n; k++)if (a[i][k]) // 小优化：只有存在转移时才计算for (int j = 0; j < n; j++)res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % MOD;return res;}
};// 矩阵快速幂：计算 a^b
// 使用二进制分解法，时间复杂度 O(n^3 * log b)
Matrix ksm(Matrix a, int b) {Matrix res(a.n);// 初始化单位矩阵for (int i = 0; i < a.n; i++) res.a[i][i] = 1;while (b) {if (b & 1) res = res * a; // 如果当前二进制位为1，乘上a的对应幂a = a * a; // a自乘，准备下一位b >>= 1; // 右移一位}return res;
}int from[MAXM], to[MAXM]; // 有向边的起点和终点
int cnt = 0; // 有向边数量，从0开始递增int main() {int n, m, t, A, B; // n:点数, m:边数, t:步数, A:起点, B:终点cin >> n >> m >> t >> A >> B;// 读入无向边，拆成两条有向边// 每条无向边对应两条有向边，编号相邻：2i 和 2i+1 互为反向边for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;from[cnt] = u; to[cnt] = v; cnt++; // 正向边from[cnt] = v; to[cnt] = u; cnt++; // 反向边}// 特判：t == 0，即不需要走任何边// 只有起点等于终点才算一种方案（停留在原地）if (t == 0) {cout << (A == B ? 1 : 0) << endl;return 0;}// 构建转移矩阵G，大小为 cnt×cnt// G[i][j] = 1 表示可以从有向边i走到有向边j（即i的终点是j的起点，且满足不走回头路条件）Matrix G(cnt);for (int i = 0; i < cnt; i++)for (int j = 0; j < cnt; j++) {// 基本条件：边i的终点 == 边j的起点（表示可以连续走这两条边）if (to[i] == from[j]) {// 附加条件：不能立即走回头路，即i和j不能是同一无向边的两条反向边// 由于有向边是成对存储的，编号i和j是反向边的条件：i == j ^ 1// 例如：边0和边1互为反向，边2和边3互为反向，依此类推if (i == (j ^ 1)) continue; // 妙用：利用异或1快速判断是否为反向边G.a[i][j] = 1; // 满足条件，设置转移为1}}// 计算 G^(t-1)，因为从一条边走到另一条边需要t-1次转移// 解释：若总步数为t，则我们需要选择第一条边（从A出发）和最后一条边（到达B），// 中间需要经过t-1次转移（边到边的转移）。Matrix M = ksm(G, t - 1);// 累加答案：枚举所有从A出发的边i和所有到达B的边j// M[i][j]表示从边i出发，经过t-1次转移到达边j的方案数int ans = 0;for (int i = 0; i < cnt; i++)if (from[i] == A) // 边i的起点是Afor (int j = 0; j < cnt; j++)if (to[j] == B) // 边j的终点是Bans = (ans + M.a[i][j]) % MOD;cout << ans << endl; // 输出答案return 0;
}