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
一行，表示答案。
Sample Input
4 5 3 0 0
0 1
0 2
0 3
2 1
3 2
0 1
0 2
0 3
2 1
3 2
Sample Output
4
HINT
对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。
对于100%的数据，N ≤ 20，M ≤ 60，t ≤ 230，0 ≤ A,B
【思路】
矩阵乘法，边点互换
题目中有不能走回头路的要求但同时存在重边。边点互换一下就可以满足这个要求啦。按照边的连接构造A矩阵并求出A^(t-1)，新建一个虚拟节点，使之向a的所有出边连通，B*A即可求出虚拟节点到各边长度为t的路径数，然后统计所有与b相连的边。
【代码】
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; const int maxn = *;
const int MOD = ;
struct Edge { int v,next;
}es[maxn<<]; struct Matrix {
int r,c,N[maxn][maxn];
void init(int r,int c) {
this->r=r,this->c=c;
memset(N,,sizeof(N));
}
Matrix operator * (const Matrix B) const{
Matrix C; C.init(r,B.c);
for(int i=;i<r;i++)
for(int j=;j<B.c;j++)
for(int k=;k<c;k++)
C.N[i][j]=(C.N[i][j]+N[i][k]*B.N[k][j])%MOD;
return C;
}
Matrix pow(int p) {
Matrix tmp=*this,ans;
ans.init(r,r);
for(int i=;i<r;i++) ans.N[i][i]=;
while(p) {
if(p&) ans=ans*tmp;
tmp=tmp*tmp; p>>=;
}
return ans;
}
}A,B; int n,m,t,a,b,u,v;
int front[maxn],en=-;
void adde(int u,int v) {
en++; es[en].next=front[u]; es[en].v=v; front[u]=en;
} int main() {
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
memset(front,-,sizeof(front));
scanf("%d%d%d%d%d",&n,&m,&t,&a,&b);
for(int i=;i<m;i++) {
scanf("%d%d",&u,&v);
adde(u,v),adde(v,u);
}
en+=;
A.init(en,en),B.init(en,en);
for(int i=front[a];i>=;i=es[i].next) B.N[en-][i]=;
for(int i=;i<n;i++) {
for(int u=front[i];u>=;u=es[u].next) {
int j=es[u].v;
for(int v=front[j];v>=;v=es[v].next)
if(u!=(v^)) A.N[u][v]++;
}
}
A=A.pow(t-);
A=B*A;
int ans=;
for(int i=front[b];i>=;i=es[i].next)
ans=(ans+A.N[en-][i^])%MOD;
printf("%d",ans);
return ;
}