先说一下边点互化的思路（貌似这种题不多？），以后看见边数少的要死的记得想边点乎化，将无向边变成有向边在考虑边之间的可达性，如果边x的终点是边y的起点（前提不是同一条边），则连一条x到y的边，表示从x可以走到y，同一条无向边转化成的两条有向边不联通（可以用最大流中异或1的方法记录两条有向边，当然也可以用一个数组记录，不过代码看起来稍恶心一点），这样就解决了题目中的限制。然后考虑如何求从a->b的长度为t的方案数，将边形成的矩阵乘t-1次，相当于经过了k-1个点，加上起点和终点k+1，中间正好经过k条边，然后有两个思路：
第一种：建立一个新矩阵，设立两个虚点（相当于原图中的虚边）使两个虚点分别与所有从出发点出发的边、所有到终点结束的边联通，用这个矩阵与刚才的矩阵相乘，统计两个虚点之间的方案数输出。
第二种：直接统计所有从出发点出发的边、所有到终点结束的边之间的方案数求和输出。
个人感觉后一种更方便一点，但是前一种也一定要会。
这题也有一个巨坑：
题目中说了有重边，所以再次理解一下题意：‘他不会立刻沿着刚刚走来的路走回’，但是他可以沿着刚刚走来的路的重边走回……
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define mod 45989
#define int LL
#define LL long long
using namespace std;
vector<int> ed[50];
int en[200],st[200];
int ni[200];
struct jz
{
LL m[200][200];
}cs;
int n,m,t,a,b;
jz operator * (jz a,jz b)
{
jz ans;memset(ans.m,0,sizeof(ans.m));
for(int i=1;i<=m*2;i++)
for(int j=1;j<=m*2;j++)
for(int k=1;k<=m*2;k++)
ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
return ans;
}
jz operator ^ (jz a,int b)
{
jz ans=a;b--;
while(b)
{
if(b&1)ans=ans*a;
a=a*a;
b=b>>1;
}
return ans;
}
signed main()
{
// freopen("in.txt","r",stdin); cin>>n>>m>>t>>a>>b;a++,b++;
int ta,tb;
for(int i=1;i<=m;i++)
{
cin>>ta>>tb;
ta++,tb++;
en[i]=tb;st[i]=ta;
en[i+m]=ta,st[i+m]=tb;
ni[i]=i+m,ni[i+m]=i;
ed[ta].push_back(i);
ed[tb].push_back(i+m);
}
for(int i=1;i<=m*2;i++)
{
for(int j=0;j<ed[en[i]].size();j++)
if(ni[i]!=ed[en[i]][j])
cs.m[i][ed[en[i]][j]]=1;
}
cs=cs^(t-1);
LL cnt=0;
for(int i=0;i<ed[a].size();i++)
for(int j=1;j<=m*2;j++)
if(en[j]==b)
cnt=(cnt+cs.m[ed[a][i]][j])%mod;
cout<<cnt%mod<<endl;
}