题面
正文
其实就是让你求有多少条长度为t的路径，但是有一个特殊条件：不能走过一条边以后又立刻反着走一次（如果两次经过同意条边中间隔了别的边是可以的）
如果没有这个特殊条件，我们很容易想到dp做法：设$dpleft[i ight]left[j ight]$表示第i个时刻（初始算0），走到第j个点的答案总数
但是这里要限制不能反复走，那么直接设点会导致信息丢失
那我们怎么样才能让保存当前所在点的情况下，不丢失最后一条边的信息呢？
答案非常显然，我们只要设$dpleft[i ight]left[j ight]$表示第i个时刻（初始算0），走到第j条边的终点（也就是刚刚经过了第j条边到达这里）的答案总数，就可以了
此时我们因为知道第j条边的所有信息，而第j条边的信息中又包括了当前所在节点，所以我们继续转移需要的信息都收集全了
转移就是从当前点$u$开始，枚举从$u$出发的边$k$，向$dpleft[i+1 ight]left[toleft(k ight) ight]$转移即可
然而这里有个问题：T太大了，直接转移肯定爆炸，那怎么办呢？
我们观察可得，对于每个$dpleft[i ight]left[j ight]$，只要$j$确定了，那么他应该往哪些状态转移也就确定了，同时这个转移一定是线性的（也就是$dp$这一项一定是一次的）
那我们还等什么呢？矩阵快速幂上啊！
我们构造转移矩阵B和初始状态矩阵A，但是这里又有一个问题：初始只有一个出发节点，并没有不能走哪条边的限制，但是转移矩阵B又依赖于这个限制，怎么办呢？
这好说，我们只要把A矩阵从所有$dpleft[0 ight]left[j ight]$变成所有$dpleft[1 ight]left[j ight]$就好了
这时答案矩阵$C=Aast B^{t-1}$
只要取出答案矩阵中所有终点是给定终点的边的答案之和，输出即可
Code
写了结构体重载运算符......慢死
还好加了读入优化苟过去了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
inline ll read(){
ll re=0,flag=1;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') flag=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re*flag;
}
ll MOD=45989;
ll n,m,op,ed,tt,cnt=0,first[110];
struct edge{//邻接表存边
ll next,to;
}a[150];
inline void add(ll u,ll v){//矩阵结构体
a[++cnt]=(edge){first[u],v};first[u]=cnt;
a[++cnt]=(edge){first[v],u};first[v]=cnt;
}
struct ma{
ll a[150][150],n,m;
ma(){memset(a,0,sizeof(a));n=m=0;}
void clear(){memset(a,0,sizeof(a));n=m=0;}
const ma operator *(const ma &b){
ma re;re.n=n;re.m=b.m;ll i,j,k;
for(i=1;i<=n;i++){
for(k=1;k<=m;k++){
if(!a[i][k]) continue;
for(j=1;j<=b.m;j++){
re.a[i][j]+=(a[i][k]*b.a[k][j]);
re.a[i][j]%=MOD;
}
}
}
return re;
}
const void operator =(const ma &b){
n=b.n;m=b.m;ll i,j;
for(i=1;i<=n;i++) for(j=1;j<=m;j++) a[i][j]=b.a[i][j];
}
}A,B;
void qpow(ma &x,ma y,ll T){
while(T){
if(T&1) x=x*y;
y=y*y;T>>=1;
}
}
ll o(ll x){return ((x%2)?(x+1):(x-1));}//求一条边的反向边（因为我是一开始编号的，所以不方便直接异或）
int main(){
memset(first,-1,sizeof(first));ll i,t1,t2,j,u;
n=read();m=read();tt=read();op=read();ed=read();op++;ed++;
for(i=1;i<=m;i++){
t1=read();t2=read();t1++;t2++;
add(t1,t2);
}
A.n=1;A.m=B.m=B.n=cnt;
for(j=1;j<=cnt;j++){//构造转移矩阵
u=a[j].to;
for(i=first[u];~i;i=a[i].next){
if(i==o(j)) continue;
B.a[j][i]+=1;
}
}
for(i=first[op];~i;i=a[i].next){//构造初始矩阵
A.a[1][i]+=1;
}
qpow(A,B,tt-1);ll ans=0;
for(i=first[ed];~i;i=a[i].next){//统计答案
ans=(ans+A.a[1][o(i)])%MOD;
}
printf("%lld",ans);
}