此题似乎有两种写法,一种是一维表示步数,一维表示边,一种是两维都表示边,类似floyd,这里是第二种
这题和裸矩阵floyd唯一的区别就是不能从上一次来的边走回去,
如果还像原来一样用点表示状态就信息不足,暂且不考虑矩快优化dp的问题,要想知道上回走的那条边不如干脆记录上回走的哪条边,这样不仅知道从哪条边走来,因为边确定了现在在哪个点也确定了,所以设$f[i][j]$为从编号为$i$的边走到编号为$j$的边的路径数,然后直接矩快即可,注意0时刻没走,矩阵全是0没法转移,所以初始时相当于已经走出一步走了一条边了,只要$t-1$次幂即可
注意边的编号从2开始
#include<bits/stdc++.h> using namespace std; const int maxn=55; const int maxm=65; const int mod=45989; inline int read(){ int ret=0,fix=1;char ch; while(!isdigit(ch=getchar()))fix=ch=='-'?-1:fix; do ret=(ret<<1)+(ret<<3)+ch-'0'; while(isdigit(ch=getchar())); return ret*fix; } int n,m,t,aa,bb; struct node{ int v,nxt; }e[maxm<<1]; int head[maxn],cnt=1; inline void add(int u,int v){ e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt; } struct mat{ int a[200][200]; // mat(){} void clear(){ memset(a,0,sizeof(a)); } }f; mat operator *(mat t1,mat t2){ mat ans;ans.clear(); for(int i=1;i<=m*2;i++) for(int j=1;j<=m*2;j++) for(int k=1;k<=m*2;k++) ans.a[i][j]=(ans.a[i][j]+t1.a[i][k]*t2.a[k][j])%mod; return ans; } mat operator^(mat a,int b){ mat ans;ans.clear(); for(int i=1;i<=m*2;i++)ans.a[i][i]=1; while(b){ if(b&1)ans=ans*a; a=a*a; b>>=1; } return ans; } int main(){ scanf("%d%d%d%d%d",&n,&m,&t,&aa,&bb);aa++,bb++; for(int i=1,u,v;i<=m;i++){ u=read();v=read();u++,v++; add(u,v);add(v,u); } for(int i=2;i<=m*2+1;i++){ for(int j=head[e[i].v];j;j=e[j].nxt){ if(j!=(i^1))f.a[i-1][j-1]=1; } } f=f^(t-1); int cnt=0; for(int i=head[aa];i;i=e[i].nxt) for(int j=2;j<=m*2+1;j++) if(e[j].v==bb)(cnt+=f.a[i-1][j-1])%=mod; printf("%d",cnt); }