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。
N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B
Output
一行，表示答案。
Sample Input
4 5 3 0 0
0 1
0 2
0 3
2 1
3 2
Sample Output
4
题解:
这题卡常啊,居然矩乘可以TLE.
本题大概思路如下:
这题因为有不能回走的要求,所以不能向平时那样直接对邻接矩阵做矩乘了,需要对边做矩乘,在矩阵中把自己和自己的位置设为0,这样可以保证不会往回走,并且注意要虚拟一个初始节点连向输入的S,最后统计答案直接将连到t的边的方案数相加即可
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=55,M=150;
int n,m,T,s,t,mod=45989,map[M][M],head[N],to[M],nxt[M],num=1;
void init(int x,int y){
nxt[++num]=head[x];to[num]=y;head[x]=num;
}
struct mat{
int a[M][M];
mat(){}
mat(int mp[M][M]){
for(RG int i=1;i<=num;i++)
for(RG int j=1;j<=num;j++)a[i][j]=mp[i][j];
}
mat operator *(const mat &p)const{
mat tmp;
for(RG int i=1;i<=num;i++)
for(RG int j=1;j<=num;j++){
tmp.a[i][j]=0;
for(RG int k=1;k<=num;k++){
tmp.a[i][j]+=(a[i][k]*p.a[k][j])%mod;
if(tmp.a[i][j]>=mod)tmp.a[i][j]-=mod;
}
}
return tmp;
}
};
void work()
{
scanf("%d%d%d%d%d",&n,&m,&T,&s,&t);
s++;t++;T--;
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
x++;y++;
init(x,y);init(y,x);
}
for(int i=head[s];i;i=nxt[i])
map[1][i]++;
for(int i=2;i<=num;i++){
for(int j=head[to[i]];j;j=nxt[j])
if(i!=(j^1))map[i][j]++;
}
mat S=mat(map),K=mat(map);
while(T){
if(T&1)S=S*K;
K=K*K;T>>=1;
}
int ret=0;
for(RG int i=2;i<=num;i++){
if(to[i]==t){
ret+=S.a[1][i];
if(ret>=mod)ret-=mod;
}
}
printf("%d
",ret);
}
int main()
{
work();
return 0;
}