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
题解
一眼就是矩乘。开始想着是用点建矩阵，但是发现不能去除走回去的影响。。
怎么办？？我们用边来建矩阵！把无向边拆成有向边
先列个方程
f[i][j]表示st~第i条边的终点，走了j步的方案数
那很明显可以从f[k][j-1]继承过来嘛对吧
就是f[i][j]=sigma(f[k][j-1])，其中k和i是相邻的边，并且需要满足k和i组合并不是一条无向边
怎么叫相邻法？
比如第i条边是x->y 第k条边是y->z 那么这两条边相邻
怎么叫组合是无向边？
比如第i条边是x->y 第k条边是y->x 那这个很明显不能继承嘛。。
然后矩阵就可以自己yy出来了。。
题目里有重边，所以限制条件还要再改一下。。就是你搜到两条x->y y->x的，按常理不能继承，但我们有重边，所以这就可以继承了。
就因为这个wa了三发
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int mod=45989;
struct node
{int x,y,next,other;
}a[2100];int len,last[2100];
void ins(int x,int y)
{int k1,k2;k1=++len;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;k2=++len;a[len].x=y;a[len].y=x;a[len].next=last[y];last[y]=len;a[k1].other=k2;a[k2].other=k1;
}
int n,m,t,st,ed;
struct matrix
{int m[200][200];matrix(){memset(m,0,sizeof(m));}
}pre,tmp;
matrix multi(matrix u,matrix v,int n,int m,int p)
{matrix s;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=1;k<=p;k++)s.m[i][k]=(s.m[i][k]+u.m[i][j]*v.m[j][k]%mod)%mod;return s;
}
matrix pow_mod(matrix u,int b)
{matrix ans;for(int i=1;i<=len;i++)ans.m[i][i]=1;while(b){if(b%2==1)ans=multi(ans,u,len,len,len);u=multi(u,u,len,len,len);b/=2;}return ans;
}
int main()
{scanf("%d%d%d%d%d",&n,&m,&t,&st,&ed);st++;ed++;len=0;memset(last,0,sizeof(last));for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);x++;y++;ins(x,y);}if(t==0){if(st==ed)printf("1\n");else printf("0\n");return 0;}for(int i=1;i<=len;i++){int x=a[i].y;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(k!=a[i].other)pre.m[i][k]++;}}for(int k=last[st];k;k=a[k].next)tmp.m[1][k]++;tmp=multi(tmp,pow_mod(pre,t-1),1,len,len);int ret=0;for(int i=1;i<=len;i++)if(a[i].y==ed)ret=(ret+tmp.m[1][i])%mod;printf("%d\n",ret);return 0;
}