https://daniu.luogu.org/problem/show?pid=2151#sub 题目就是说我们不可以回走； 但是环还是可以的； 如果上次1->3 现在不可以直接3->1 但是过一会再再走是可以的； 所以我们把边变成2个点； 边与边链接的时候发现这种情况就不连，这不就好了嘛； 然后快速幂t-1次，因为这个是边； 然后现在要求所有S点连出的边到所有E点连入的边的方案； 这个就乱搞好了
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define Ll long long using namespace std; struct cs{int to,nxt;}a[1000]; struct jv{ int n,m; int a[125][125]; jv(){memset(a,0,sizeof a);} }c,ans; int head[1000],ll=1; int n,m,t,x,y,S,E,sum; jv cheng(jv a,jv b){ jv c;c.n=a.n;c.m=b.m; for(int i=1;i<=c.n;i++) for(int k=1;k<=a.m;k++)if(a.a[i][k]) for(int j=1;j<=c.m;j++) c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%45989; return c; } jv ksm(int k){ jv ans=c; for(k--;k;k>>=1,c=cheng(c,c)) if(k&1)ans=cheng(ans,c); return ans; } void init(int x,int y){ a[++ll].to=y; a[ll].nxt=head[x]; head[x]=ll; } void make(){ c.n=c.m=ll; for(int i=2;i<=ll;i++) for(int k=head[a[i].to];k;k=a[k].nxt) if(i!=(k^1))c.a[i][k]++; ans.n=ans.m=ll; for(int k=head[S];k;k=a[k].nxt) ans.a[1][k]=1; } int main() { scanf("%d%d%d%d%d",&n,&m,&t,&S,&E);S++;E++; for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y); x++;y++; init(x,y);init(y,x); } make(); ans=cheng(ans,ksm(t-1)); for(int i=2;i<=ll;i++) if(a[i].to==E)sum=(sum+ans.a[1][i])%45989; printf("%d",sum); }