Aimee

首先的问题，如果这个题是无向图怎么搞，显然dp[i][j]表示到点i走了j步就可以了。

但是这是无向图啊，怎么搞呢

那就统计一下从那条边来的，也就是i表示从i边结束

然后暴力转移显然，但是tle起飞

显然可以用矩阵优化一下。

下标很重要，因为矩阵乘法的美妙性质。

最后的统计的时候正难则反，统计反向的边。

结构体是个好东西，妥善利用起来，还有重载，减少码量。

更详细的题解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,t,S,T;
int mod=45989;
int x,y;
struct edge{
    int to;
    int f;
    int ne;
}ed[150];
int head[60];
int p=0;
int ans[160][160];
int l;
int tem[160][160];
int fa[160][160];
int org[160][160];
void power(int n){
    while(n){
        if(n&1){
            for(int i=1;i<=l;++i){
                for(int j=1;j<=l;++j){
                    tem[i][j]=0;
                    for(int k=1;k<=l;++k){
                        tem[i][j]+=org[i][k]*ans[k][j];
                        tem[i][j]%=mod;
                    }
                }
            }
            for(int i=1;i<=l;++i){
                for(int j=1;j<=l;++j){
                    ans[i][j]=tem[i][j];
                }
            }
        }
        n>>=1;
        for(int i=1;i<=l;++i){
            for(int j=1;j<=l;++j){
                tem[i][j]=0;
                for(int k=1;k<=l;++k){
                    tem[i][j]+=org[i][k]*org[k][j];
                    tem[i][j]%=mod;
                }
            }
        }
        for(int i=1;i<=l;++i){
            for(int j=1;j<=l;++j){
                org[i][j]=tem[i][j];
            }
        }
    }
    return ;
}
int op(int x){
    return (x&1) ?x+1:x-1;
}
int znx;
void add(int f,int to){
    ed[++p].f=f;
    ed[p].to=to;
    ed[p].ne=head[f];
    head[f]=p;
}
signed main(){
    scanf("%d%d%d%d%d",&n,&m,&t,&S,&T);
    S++;
    T++;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        x++;
        y++;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=p;++i){
        for(int  k=head[ed[i].to];k;k=ed[k].ne){
            if(k!=op(i)){
                org[k][i]++;
            }
        }   
    }
    l=p;
    for(int i=1;i<=p;++i){
        ans[i][i]=1;
    }
    for(int i=head[S];i;i=ed[i].ne){
        fa[i][1]++;
    }
    power(t-1);
    for(int i=1;i<=l;++i){
            for(int j=1;j<=l;++j){
                tem[i][j]=0;
                for(int k=1;k<=l;++k){
                    tem[i][j]+=ans[i][k]*fa[k][j];
                    tem[i][j]%=mod;
                }
            }
        }
    for(int i=head[T];i;i=ed[i].ne){
        znx=(znx+tem[op(i)][1])%45989;
    }
    cout<<znx;
    return 0;
}