传送门

朝奈池扔了$400$多个石头没出货啊啊啊啊啊

一个非常显然的$DP$：

设$f(i,j,k)$表示时间$i$到达$j$点，上一条经过的边为$k$。

一个非常显然的转移：

$f(i,j,k)\rightarrow f(i+1,edge(l).to,l)(l\neq k)$

用矩乘优化一波，但这样我们发现矩阵大小是$2nm$的，跑不动。

每个点的入边条数是有限的，所以很多状态是无用的，对每个点的所有入边在矩阵上开元素就行了。矩阵大小缩小到$2m$。

总复杂度$O((2m)^3\log t)$。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>

#define maxn 100005
#define inf 0x3f3f3f3f

const int mod = 45989;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int f[105][55][55],ma[55][65],id[55][65];
vector<int>e[55];
struct Matrix{
    int a[130][130],l,c;
    Matrix operator * (const Matrix &x){
        Matrix ans;
        ans.l=l,ans.c=x.c;
        for(register int k=0;k<c;++k)
            for(register int i=0;i<=l;++i)
                for(register int j=0;j<x.c;++j)
                    ans.a[i][j]=(ans.a[i][j]+a[i][k]*x.a[k][j]%mod)%mod;                    
        return ans;
    }
    Matrix operator ^ (int y){
        Matrix ans=*this,x=ans;
        --y;
        while(y){
            if(y&1)ans=ans*x;
            x=x*x,y>>=1;
        }
        return ans;
    }
    Matrix(){memset(a,0,sizeof a);}
}tr,start;
int main(){
    int n=read(),m=read(),L=read(),s=read()+1,t=read()+1,cnt=0;
    while(m--){
        int x=read()+1,y=read()+1;
        e[x].push_back(y),e[y].push_back(x);
        ma[x][e[x].size()-1]=e[y].size()-1;
        ma[y][e[y].size()-1]=e[x].size()-1;
    }
    for(register int i=1;i<=n;++i)
        for(register int j=0;j<e[i].size();++j)
            id[i][j]=cnt++;
    start.l=1,start.c=tr.l=tr.c=cnt;
    for(register int i=1;i<=n;++i)
        for(register int j=0;j<e[i].size();++j)
            for(register int k=0;k<e[i].size();++k)
                if(j!=k)++tr.a[id[i][j]][id[e[i][k]][ma[i][k]]];
    for(register int i=0;i<e[s].size();++i)
        ++start.a[0][id[e[s][i]][ma[s][i]]];
    start=start*(tr^(L-1));
    int ans=0;
    for(register int i=0;i<e[t].size();++i)(ans+=start.a[0][id[t][i]])%=mod;
    printf("%d\n",ans);
}