我的代码发给你，可以用来对拍。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 51, M = 61, mod = 45989;
int n, m, t, S, T, u, v;
int cntE, head[N], to[M << 1];
struct Edge{int u, v;}e[M << 1];
void addEdge(int u, int v)
{
e[++cntE] = (Edge){u, v};
to[cntE] = head[u];
head[u] = cntE;
}
struct Matrix
{
#define uint unsigned long long
#define __ERROR_OF_NOT_FIT_MATRIX__ 893167885
uint row, col;
vector<vector<int> > mat;
Matrix(int R, int C)
{
row = R, col = C;
vector<int> __ROW_OF_MATRIX__;
__ROW_OF_MATRIX__.assign(C + 1, 0);
mat.assign(R + 1, __ROW_OF_MATRIX__);
}
Matrix(int R, int C, int num)
{
row = R, col = C;
vector<int> __ROW_OF_MATRIX__;
__ROW_OF_MATRIX__.assign(C + 1, num);
mat.assign(R + 1, __ROW_OF_MATRIX__);
}
Matrix operator +(const Matrix& ADD)
{
if (row != ADD.row || col != ADD.col) exit(__ERROR_OF_NOT_FIT_MATRIX__);
Matrix RET(row, col);
for (uint r = 0; r <= row; ++r)
for (uint c = 0; c <= col; ++c)
RET.mat[r][c] = mat[r][c] + ADD.mat[r][c];
return RET;
}
Matrix operator *(const Matrix& MUL)
{
if (col != MUL.row) exit(__ERROR_OF_NOT_FIT_MATRIX__);
Matrix RET(row, MUL.col);
for (uint r = 0; r <= row; ++r)
for (uint c = 0; c <= MUL.col; ++c)
for (uint k = 0; k <= col; ++k)
RET.mat[r][c] += mat[r][k] * MUL.mat[k][c];
return RET;
}
Matrix operator %(const int& MOD)
{
Matrix RET(row, col);
for (uint r = 0; r <= row; ++r)
for (uint c = 0; c <= col; ++c)
RET.mat[r][c] = mat[r][c] % MOD;
return RET;
}
Matrix operator ^(const uint& INDEX)
{
if (row != col) exit(__ERROR_OF_NOT_FIT_MATRIX__);
Matrix RET = *this, BASE = *this;
uint __INDEX = INDEX - 1;
while (__INDEX) {
if (__INDEX & 1) RET = RET * BASE;
BASE = BASE * BASE, __INDEX >>= 1;
}
return RET;
}
Matrix operator ^(const pair<uint, int>& PAIR_INDEX)
{
if (row != col) exit(__ERROR_OF_NOT_FIT_MATRIX__);
Matrix RET(this -> row, this -> col), BASE = *this;
const int MOD = PAIR_INDEX.second;
for (uint i = 1; i <= row; ++i) RET.mat[i][i] = 1;
uint INDEX = PAIR_INDEX.first;
while (INDEX) {
if (INDEX & 1) RET = RET * BASE % MOD;
BASE = BASE * BASE % MOD, INDEX >>= 1;
}
return RET;
}
};
int calc(int x)
{
return x & 1? x + 1 : x - 1;
}
signed main()
{
cin >> n >> m >> t >> S >> T, ++S, ++T;
if (t == 0) return cout << (S == T) << endl, 0;
for (int i = 1; i <= m; ++i) {
cin >> u >> v, ++u, ++v;
addEdge(u, v);
addEdge(v, u);
}
Matrix B(cntE, cntE);
for (int i = 1; i <= cntE; ++i)
for (int j = head[e[i].v]; j; j = to[j])
if (j != calc(i)) ++B.mat[j][i];
Matrix A(cntE, cntE);
for (int i = head[S]; i; i = to[i]) ++A.mat[i][1];
B = B ^ make_pair(t - 1, mod);
B = B * A;
int ans = 0;
for (int i = head[T]; i; i = to[i]) ans = (ans + B.mat[calc(i)][1]) % mod;
cout << ans << endl;
return 0;
}
```
by Composite_Function @ 2024-04-14 18:28:24
OKOK
@[Composite_Function](/user/531746)
我发现是if(i!=(j^1))应该改成i-1，j-1
by xiaoliebao1115 @ 2024-04-19 19:24:39