题目link：https://www.luogu.com.cn/problem/P2151
Part0：
注意题目有重边。
Part1：
首先这道题的题目限制为走过一条边不能按原边返回，这就导致了这个图的有向性，从而得出需要拆边的结论。
Part2：
拆完边后，容易看出如果要想满足题目限制，那么相当于走过第 $i$ 条边后，除了 $i$ 的反向边都可以走。
Part3：
得到上述特性后，再来观察题目，发现数据范围里的 $m$ 的值比较小，且比较的特殊，但是注意，因为通过 Part1 和 Part2 已经拆完边了，那么边的数量需要 $*$ $2$ 。
众所周知，这道题要求的路径方案数和邻接矩阵的幂次方有很大的关系，再加上 $2$ $*$ $m$ $=$ $120$ 这个值，发现 $120^3$ $*$ $log$ $t$ （矩阵快速幂的复杂度为 $O($$n^3$ $log$ $k$$)$）约为 $5e7$ ，不会超时，因此考虑用 $2$ $*$ $m$ 为行列的大小建一个矩阵。
Part4：
建完矩阵后，容易发现矩阵中的元素的一种恰当且显然的意义为如果第 $i$ 条边的终点是第 $j$ 条边的起点 $\&\&$ 第 $i$ 条边和第 $j$ 条边不是反向边，那么矩阵中的第 $i$ 行第 $j$ 列的元素就是 $1$ ，否则为 $0$ 。
Part5：
考虑矩形的 $k$ 次方是什么含义，设 $k$ 次方之后的矩形为 $A$ ，那么容易得出 $A_{i, j}$ 是在图上第 $i$ 条边经过 $k$ $+$ $1$ 条边到达第 $j$ 条边（包括第 $i$ 条边和第 $j$ 条边）的方案数。
Part6：
这样，便容易得出求答案的方法为：在建完矩阵后用矩阵快速幂求出它的 $t$ $-$ $1$ 次方（注意不是 $t$ 次方），枚举起点 $a$ 的所有出边和终点 $b$ 的所有入边，累加计算一下就好了。
Code：
1 #include <cstdio>
2
3 typedef long long LL;
4
5 const int MAXM = 60;
6 const LL MOD = 45989;
7
8 int n, m, t, a, b;
9 int outA[MAXM + 5], inB[MAXM + 5], cntA, cntB, cntEdge;
10
11 struct Node {
12 int st, to;
13 };
14
15 struct Mat {
16
17 int N;
18 LL arr[2 * MAXM + 5][2 * MAXM + 5];
19
20 Mat() {}
21 Mat(int _N, LL val = 0ll) {
22 N = _N;
23 for(int i = 1; i <= N; ++i) {
24 for(int j = 1; j <= N; ++j) {
25 arr[i][j] = (i == j) ? val : 0ll;
26 }
27 }
28 }
29
30 // void print() {
31 // for(int i = 1; i <= N; ++i) {
32 // for(int j = 1; j <= N; ++j) {
33 // printf("%d%c", arr[i][j], (j == N - 1) ? '\n' : ' ');
34 // }
35 // }
36 // puts("");
37 // }
38
39 };
40
41 Mat operator* (const Mat &A, const Mat &B) {
42
43 Mat res(A.N);
44
45 for(int i = 1; i <= res.N; ++i) {
46 for(int j = 1; j <= res.N; ++j) {
47 for(int k = 1; k <= res.N; ++k) {
48 res.arr[i][j] += A.arr[i][k] * B.arr[k][j];
49 res.arr[i][j] %= MOD;
50 }
51 }
52 }
53
54 return res;
55 }
56
57 Mat qpow(Mat A, int k) {
58
59 Mat res(A.N, 1ll);
60
61 for(; k; k >>= 1) {
62 if(k & 1) res = res * A;
63 A = A * A;
64 }
65
66 return res;
67 }
68
69 int main() {
70
71 scanf("%d %d %d %d %d", &n, &m, &t, &a, &b);
72
73 Node edge[2 * MAXM + 5]; // 存边
74 for(int i = 1, x, y; i <= m; ++i) {
75 scanf("%d %d", &x, &y);
76 edge[++cntEdge].st = x, edge[cntEdge].to = y;
77 edge[++cntEdge].st = y, edge[cntEdge].to = x;
78 if(x == a || y == a) { // 记录起点和终点的出边和入边
79 outA[++cntA] = (x == a) ? cntEdge - 1 : cntEdge;
80 }
81 if(x == b || y == b) {
82 inB[++cntB] = (x == b) ? cntEdge : cntEdge - 1;
83 }
84 }
85
86 Mat fac(2 * m); // 建矩阵
87 for(int i = 1; i <= cntEdge; ++i) {
88 for(int j = 1; j <= cntEdge; ++j) {
89 if(i == j || ((i & 1) && (j == i + 1)) || ((!(i & 1)) && (j == i - 1))) continue;
90 if(edge[i].to == edge[j].st) {
91 fac.arr[i][j] = 1ll;
92 }
93 }
94 }
95
96 fac = qpow(fac, t - 1); // 矩阵快速幂
97
98 LL ans = 0; // 枚举出入边求解
99 for(int i = 1; i <= cntA; ++i) {
100 for(int j = 1; j <= cntB; ++j) {
101 ans += fac.arr[outA[i]][inB[j]];
102 ans %= MOD;
103 }
104 }
105
106 printf("%lld\n", ans);
107
108 return 0;
109 }