题目大意

给定一个有$n$个点，$m$条边的无向图，每条边的长度都是$1$，没有自环，可能有重边

给定起点$A$与终点$B$，求从起点走$t$条边到达终点的边集个数

注意，每一条选取的边不能是刚刚加入边集的边

数据范围

$n\leqslant 20,m\leqslant 60,t\leqslant 2^{30},0\leqslant A,B$

题解

一开始看到数据范围中的$t\leqslant 2^{30}$，就可以猜想用快速幂矩阵乘法来优化问题了

这道题要求不能走上一条来的边，则可以把无向边分成两条有向边，通过判断有向边之间是否首尾相连建立矩阵$M$

矩阵$M$中$a[i][j]$表示第$i$条有向边走一步可以到第$j$条有向边的方案数（可能有重边）`

然后把矩阵$M$自乘$t-1$次就可以使得，$a[i][j]$表示第$i$条有向边走$t$步可以到第$j$条有向边的方案数

最后创建记录一个从起点$A$，走一步到达任意一条有向边的矩阵$N$，与矩阵$M$相乘得到矩阵$L(L=N\times M)$

直接统计起点$A$到与链接终点$B$的边的方案数之和就是答案了

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}


int n,m,t,A,B,sum,et=1;
struct edge{int from,to,next;}e[200];
int last[50],a[200][200],b[200][200],ans[200][200];
inline void addedge(int u,int v){
    e[++et]=(edge){u,v,last[u]};last[u]=et;
    e[++et]=(edge){v,u,last[v]};last[v]=et;
}
inline void mul(int a[200][200],int b[200][200],int result[200][200]){
    int c[200][200];memset(c,0,sizeof(c));
    For(i,1,et) For(j,1,et)
        For(p,1,et) c[i][j]=(c[i][j]+a[i][p]*b[p][j])%45989;
    For(i,1,et) For(j,1,et) result[i][j]=c[i][j];
}

int main(){
    n=read(),m=read(),t=read()-1,A=read(),B=read();
    For(i,1,m) addedge(read(),read());
    For(i,2,et) For(j,2,et)
        if ((e[i].to==e[j].from)&&(i!=(j^1))) a[i][j]++;
    goedge(i,A) b[1][i]++;
    For(i,1,et) ans[i][i]=1;
    while (t){
        if (t&1) mul(ans,a,ans);
        t>>=1;mul(a,a,a);
    }
    mul(b,ans,b);
    goedge(i,B) sum=(sum+b[1][i^1])%45989;
    printf("%d\n",sum);
    return 0;
}