【题意】给定n个点m边的无向图，求A到B恰好经过t条边的路径数，路径须满足每条边都和前一条边不同。n<=20,m<=60,t<=2^30。

【算法】矩阵快速幂

【题解】将图的邻接矩阵进行矩阵快速幂就可以得到恰好经过t条边的路径数，但不能满足题目要求。

改为对原图的边进行相互连边，将经过同一个点的边两两连边，这样就是新邻接矩阵的t-1步。

为了满足题目要求，当两条边互为反向边时不连边即可。

最后乘上从A出发的边的矩阵，然后统计到达B的路径数。

复杂度O((m*2)^3 log t)。

#include
      
       #include
       
        const int maxn=130,MOD=45989;int n,m,t,A,B,a[maxn][maxn],ans[maxn][maxn],c[maxn][maxn],tot=1,first[maxn];struct edge{
    int v,from;}e[maxn]; void multply(int a[maxn][maxn],int b[maxn][maxn]){    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)c[i][j]=0;    for(int i=1;i<=n;i++)        for(int k=1;k<=n;k++)            for(int j=1;j<=n;j++)c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=c[i][j];}void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}int main(){    scanf("%d%d%d%d%d",&n,&m,&t,&A,&B);A++;B++;    for(int i=1;i<=m;i++){        int u,v;        scanf("%d%d",&u,&v);        insert(++u,++v);insert(v,u);    }    for(int i=2;i<=tot;i++){        for(int j=first[e[i].v];j;j=e[j].from)if(i!=(j^1)){            a[i][j]++;        }    }    for(int i=first[A];i;i=e[i].from)a[1][i]++;//    n=tot;    for(int i=1;i<=n;i++)ans[i][i]=1;    while(t){        if(t&1)multply(ans,a);        multply(a,a);        t>>=1;    }    int ANS=0;    for(int i=first[B];i;i=e[i].from)ANS=(ANS+ans[1][i^1])%MOD;    printf("%d",ANS);    return 0;}