Description
HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间 内，走过一定的距离。 但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。 现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地 点A走到给定地点B共有多少条符合条件的路径.
Input
第一行：五个整数N，M，t，A，B。其中N表示学校里的路口的个数，M表示学校里的 路的条数，t表示HH想要散步的距离，A表示散步的出发点，而B则表示散步的终点。 接下来M行，每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。数据保证Ai = Bi，但 不保证任意两个路口之间至多只有一条路相连接。 路口编号从0到N ? 1。 同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。 答案模45989。
Output
一行，表示答案。
Solution
不要停下来啊！
直接无脑转移再用矩阵快速幂优化。
注意要用边dp，因为不能走回头路。
Code
#include<bits/stdc++.h>
using namespace std;
const int mod=45989;
int n,m,a,b;
long long t;
vector<int>g[110];
struct Matrix{int a[121][121];Matrix(){memset(a,0,sizeof(a));}
}u,v,w;
Matrix operator *(const Matrix& u,const Matrix& v){Matrix c;for(int i=1;i<=2*m;i++)for(int j=1;j<=2*m;j++)for(int k=1;k<=2*m;k++)c.a[i][j]=(c.a[i][j]+u.a[i][k]*v.a[k][j]%mod)%mod;return c;
}
Matrix pow(long long n){Matrix s=u,bas=v;while(n){if(n&1) s=s*bas;bas=bas*bas;n>>=1;// for(int i=1;i<=2*m;i++){
// cout<<s.a[1][i]<<" ";
// }
/// cout<<endl;
/// for(int i=1;i<=2*m;i++){
/// for(int j=1;j<=2*m;j++){
/// cout<<bas.a[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl<<endl;}return s;
}
bool tb[210];
int main(){int x,y;scanf("%d%d%lld%d%d",&n,&m,&t,&a,&b); a++,b++;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y); x++,y++;g[x].push_back(i);g[y].push_back(m+i);if(x==b) tb[m+i]=1;if(y==b) tb[i]=1;if(x==a) u.a[1][i]=1;if(y==a) u.a[1][m+i]=1;}for(int i=1;i<=n;i++)for(int j=0;j<g[i].size();j++)for(int k=j+1;k<g[i].size();k++){int y=g[i][j],z=g[i][k];v.a[(y+m-1)%(2*m)+1][z]=1;v.a[(z+m-1)%(2*m)+1][y]=1;//cout<<i<<" "<<y<<" "<<z<<" "<<(y-1)%10+1<<" "<<(z-1)%10+1<<endl;}
// for(int i=1;i<=2*m;i++)
// cout<<u.a[1][i]<<" ";cout<<endl<<endl;
// for(int i=1;i<=2*m;i++){
// for(int j=1;j<=2*m;j++){
// cout<<v.a[i][j]<<" ";
// }
// cout<<endl;
// }
/// cout<<endl;w=pow(t-1);int ans=0;for(int i=1;i<=2*m;i++)if(tb[i]) ans+=w.a[1][i];printf("%d",ans%mod);
}