Description：

从 $S$ 走到 $T$ 不连续重复经过某条边（即不走过去再走回来） $d$ 步的方案数。

$1\le N \le 50$ $1\le M\le 60$ $1\le d \le 2^{30}$

Solution：

想到 $floyed$ 求路径，对于限制，将上一条转移过来的边加入到矩阵中一块转移，发现经过上一条转移过来的边后，所在的位置只能是边的两端，于是设计矩阵为 $f[i][0/1][j][0/1]$ 表示从边 $i$ 的左/右端，经过 $j$ 转移到 $j$ 的左/右端。对于起始，构造一个向量表示经过一条边的状态；对于结束，统计所有能到 $T$ 的状态。

矩阵快速幂加速，时间复杂度 $O(60\times2\times60\times2\times log_22^{30})$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 45989

#define rint register int

int n,m,d,s,t;

#define MAXM 61

#define MAXN 51

int f[MAXM][2][MAXM][2];

int res[MAXM][2][MAXM][2];

int st[MAXM][2];

int end[MAXM][2];

struct edge

{

    int to,nxt,id,type;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b,int c)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];e[edgenum].id = c;e[edgenum].type = 0;lin[a] = edgenum;

    ++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];e[edgenum].id = c;e[edgenum].type = 1;lin[b] = edgenum;

    return;

}

int c[MAXM][2][MAXM][2];

inline void mul(int a[MAXM][2][MAXM][2],int b[MAXM][2][MAXM][2])

{

	for(rint i = 1;i <= m;++i)

	{

		for(rint ii = 0;ii <= 1;++ii)

		{

			for(rint j = 1;j <= m;++j)

			{

				for(rint jj = 0;jj <= 1;++jj)

				{

					for(rint k = 1;k <= m;++k)

					{

						for(rint kk = 0;kk <= 1;++kk)

						{

							c[i][ii][j][jj] = (c[i][ii][j][jj] + a[i][ii][k][kk] * b[k][kk][j][jj] % MOD) % MOD;

						}

					}

				}

			}

		}

	}

	for(rint i = 1;i <= m;++i)

	{

		for(rint ii = 0;ii <= 1;++ii)

		{

			for(rint j = 1;j <= m;++j)

			{

				for(rint jj = 0;jj <= 1;++jj)

				{

					a[i][ii][j][jj] = c[i][ii][j][jj];

					c[i][ii][j][jj] = 0;

				}

			}

		}

	}

}

inline int read()

{

	rint res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

	n = read();m = read();d = read();s = read();t = read();

    for(rint i = 1;i <= m;++i)

    {

        add(read(),read(),i);

    }

    for(rint k = 1;k <= 2 * m;++k)

    {

		if(e[k].to == s)

		{

			st[e[k].id][e[k].type] = 1;

		}

	}

    for(rint k = 1;k <= m;++k)

	{

		for(rint i = lin[e[k * 2].to];i != 0;i = e[i].nxt)

		{

			if(e[k * 2 - 1].id == e[i].id)continue; 

			f[k][e[k * 2 - 1].type][e[i].id][e[i].type ^ 1] = 1;

		}

		for(rint i = lin[e[k * 2 - 1].to];i != 0;i = e[i].nxt)

		{

			if(e[k * 2].id == e[i].id)continue;

			f[k][e[k * 2].type][e[i].id][e[i].type ^ 1] = 1;

		}

	}

	d--;

	for(rint i = 1;i <= m;++i)

	{

		for(rint j = 0;j <= 1;++j)

		{

			res[i][j][i][j] = 1;

		}

	}

	while(d > 0)

	{

		if(d & 1)mul(res,f);

		d = d >> 1;

		mul(f,f);

	}

	for(rint i = 1;i <= m;++i)

	{

		for(rint ii = 0;ii <= 1;++ii)

		{

			for(rint j = 1;j <= m;++j)

			{

				for(rint jj = 0;jj <= 1;++jj)

				{

					end[i][ii] = (end[i][ii] + st[j][jj] * res[j][jj][i][ii] % MOD) % MOD;

				}

			}

		}

	}

	int ans = 0;

	for(rint i = lin[t];i != 0;i = e[i].nxt)

	{

		ans = (ans + end[e[i].id][e[i].type]) % MOD;

	}

	printf("%d\n",ans);

    return 0;

}