HH Go for a walk

Topic link ：luogu P2151

The main idea of the topic

Here's an undirected graph , Then give you the number of paths from the beginning to the end , Then every time you walk, you can't go back on that side , Then ask how many walking plans you have .

Ideas

First, let's talk about the normal practice .（ Happy ）
If you can go back, it's simple , But you can't look back , Consider distinguishing it .
Or you can see the edge as directed , Then see it as a point , The two edges cannot be connected , You can run matrix multiplication normally .

Here is a kind of follow $m$ Irrelevant practice .
set up $f_{x,y,z}$ For the last two points are $x,y$, go $z$ Step scheme .（ In this way, you can prevent turning back ）
$f_{x,y,z}=g_{x,y}\sum _{i=1}^n{f}_{i,x,z-1}-f_{y,x,z-1}$

But the side length of the matrix is $n^2$ no way （ Or not good enough , Not very good somewhere ）
Consider what your answer requires （$\sum _{i=1}^n{f}_{i,T,L}$）

$g{1}_{x,z}=\sum _{i=1}^n{f}_{x,i,z}=\sum _{i=1}^n(g_{x,i}\sum _{j=1}^n{f}_{j,x,z-1}-f_{i,x,z-1})=\sum _{i=1}^n{g}_{x,i}g{2}_{x,z-1}-g{2}_{x,z-1}=g{2}_{x,z-1}(\sum _{i=1}^n{g}_{x,i}-1)$
$g{2}_{y,z}=\sum _{i=1}^n{f}_{i,y,z}=\sum _{i=1}^n(g_{i,y}\sum _{j=1}^n{f}_{j,i,z-1}-f_{y,i,z-1})=\sum _{i=1}^n{g}_{x,i}g{2}_{i,z-1}-g{1}_{y,z-1}$

Then make these two things , You find that you can only keep these two information for matrix multiplication , Then the side length of the matrix becomes $2n$ You can pass ！

Then if multiple groups ask different $L,T$, Then change the fast power into Multiplication , It's the same thing .

Code

#include<cstdio>
#include<cstring>
#define ll long long
//#define mo 998244353
#define mo 45989

using namespace std;

const int N = 105;
int n, m, Q, S, T, g[N][N];
int st[N << 1], jump[60][N << 1][N << 1], ans[N << 1], tmp[N << 1];
ll L;

int add(int x, int y) {
    return x + y >= mo ? x + y - mo : x + y;}
int mul(int x, int y) {
    return 1ll * x * y % mo;}

void Init() {
    
	for (int i = 1; i <= n; i++) st[S] = add(st[S], g[S][i]);
	for (int i = 1; i <= n; i++) st[n + i] = add(st[n + i], g[S][i]);
	for (int i = 1; i <= n; i++) {
    //g1
		int tmp = mo - 1; for (int j = 1; j <= n; j++) tmp = add(tmp, g[i][j]);
		jump[0][n + i][i] = tmp;
	}
	for (int i = 1; i <= n; i++) {
    //g2
		for (int j = 1; j <= n; j++) jump[0][n + j][n + i] = add(jump[0][n + j][n + i], g[i][j]);
		jump[0][i][n + i] = add(jump[0][i][n + i], mo - 1);
	}
	for (int z = 1; z < 60; z++) {
    
		for (int k = 1; k <= (n << 1); k++)
			for (int i = 1; i <= (n << 1); i++)
				for (int j = 1; j <= (n << 1); j++)
					jump[z][i][j] = add(jump[z][i][j], mul(jump[z - 1][i][k], jump[z - 1][k][j]));
	}
}

int main() {
    
// freopen("ancient.in", "r", stdin);
// freopen("ancient.out", "w", stdout);
	
// scanf("%d %d %d %d", &n, &m, &Q, &S);
	scanf("%d %d %d %d %d", &n, &m, &L, &S, &T); S++; T++;
	for (int i = 1; i <= m; i++) {
    
		int x, y; scanf("%d %d", &x, &y);
		x++; y++;
		g[x][y]++; g[y][x]++;
	}
	
	Init();
	
// while (Q--) {
    
// scanf("%d %lld", &T, &L);
// if (!L) {printf("%d\n", (S == T) ? 1 : 0); continue;}
		if (!L) {
    printf("%d\n", (S == T) ? 1 : 0); return 0;}
		
		L--; memcpy(ans, st, sizeof(ans));
		for (int z = 59; z >= 0; z--) if ((L >> z) & 1) {
    
			for (int k = 1; k <= (n << 1); k++)
				for (int j = 1; j <= (n << 1); j++)
					tmp[j] = add(tmp[j], mul(ans[k], jump[z][k][j]));
			memcpy(ans, tmp, sizeof(ans)); memset(tmp, 0, sizeof(tmp));
		}
		printf("%d\n", ans[n + T]);
// }
	
	return 0;
}