发现\(n,m\)非常小而\(t\)非常大，所以果断考虑矩阵。
这道题如果不限制“不能立即沿刚刚过来的路回去”，就直接用邻接矩阵求\(t\)次幂然后直接调用\(ans[a][b]\)就好了。
加上限制后，我们用点就比较难考虑了，因为点是无方向的。
我们可以试着用边来转移，和点相同地，每条边记录自己可以直接到达哪些边，只需要额外限制不能走自己的反边回去即可。将\(F[i][j]\)作为转移矩阵，表示边\(i\)到边\(j\)的路径数量。初始时，对于\(u,v\)两条满足条件的边，令\(F[u][v]=1\)。
将\(G\)作为初始矩阵，点\(a\)的邻接边都设为\(1\)，用\(G\times F^{t-1}\)统计答案即可。除了转点为边以外，其他做法与点均没什么区别。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mod 45989
#define N 52
#define MM 122
using namespace std;
struct edge{int nxt,to;}e[MM];
int n,m,t,a,b,idx,head[N],base[MM][MM],ans[MM][MM],tmp[MM][MM],res;
void add(int u,int v){e[idx]={head[u],v},head[u]=idx++;}
void mul(int to[MM][MM],int a[MM][MM],int b[MM][MM]){
memset(tmp,0,sizeof tmp);
for(int i=0;i<idx;i++) for(int j=0;j<idx;j++) for(int k=0;k<idx;k++)
tmp[i][j]+=(a[i][k]*b[k][j])%mod,tmp[i][j]%=mod;
memcpy(to,tmp,sizeof tmp);
}
void qpow(int n){
while(n){
if(n&1) mul(ans,ans,base);
mul(base,base,base),n>>=1;
}
}
signed main(){
memset(head,-1,sizeof head);
cin>>n>>m>>t>>a>>b;
for(int i=1,u,v;i<=m;i++)
cin>>u>>v,add(u,v),add(v,u);
for(int i=0;i<idx;i++)
for(int j=head[e[i].to];~j;j=e[j].nxt)
if(j!=(i^1)) base[i][j]=1;
for(int i=head[a];~i;i=e[i].nxt) ans[0][i]++;
//这里选[0,idx)哪一个值作为答案的行都可以，qpow会将此行保留，其他行置为0
qpow(t-1);
for(int i=head[b];~i;i=e[i].nxt) res+=ans[0][i^1],res%=mod;
cout<<res;
return 0;
}
还有一种方法，将所有节点下标\(+1\)，建立节点\(0\)向\(a\)连一条边\(u\)，这样\(F\)就增加了\(1\)维。此时\(F^t\)的第\(0\)行即为答案。这是因为此时的初始矩阵只有\(G[0]=1\)，所以用\(G\)乘这一步可以直接省去。就不放代码了。
标签：head,P2151,MM,题解,矩阵,int,add,SDOI2009,define From： https://www.cnblogs.com/Sinktank/p/18562975