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
0 1
0 2
0 3
2 1
3 2
Sample Output
4
题解
我们将无向边拆成两条有向边，边点互换，就可以求出满足题意的解了。
//It is made by Awson on 2017.10.12
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define LL long long
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Abs(x) ((x) < 0 ? (-(x)) : (x))
using namespace std;
const int MOD = ; int n, m, t, a, b, u, v;
int f[][];
struct tt {
int to, next;
}edge[];
int path[], top = -;
struct mat {
int a[][];
mat () {
memset(a, , sizeof(a));
}
mat (int _a[][]) {
for (int i = ; i <= top; i++)
for (int j = ; j <= top; j++)
a[i][j] = _a[i][j];
}
mat operator * (const mat &b) const{
mat ans;
for (int i = ; i <= top; i++)
for (int j = ; j <= top; j++)
for (int k = ; k <= top; k++)
(ans.a[i][j] += a[i][k]*b.a[k][j]) %= MOD;
return ans;
}
}S, T; void add(int u, int v) {
edge[++top].to = v;
edge[top].next = path[u];
path[u] = top;
}
void work() {
memset(path, -, sizeof(path));
scanf("%d%d%d%d%d", &n, &m, &t, &a, &b);
for (int i = ; i <= m; i++) {
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
if (t == ) {
int ans = ;
for (int i = path[a]; i != -; i = edge[i].next)
ans += edge[i].to == ;
printf("%d\n", ans);
return;
}
for (int i = ; i <= top; i++)
for (int j = path[edge[i].to]; j != -; j = edge[j].next)
if (i != (j^)) f[i][j]++;
S = mat(f), T = mat(f);
t -= ;
while (t) {
if (t&) S = S*T;
t >>= ;
T = T*T;
}
int ans = ;
for (int i = path[a]; i != -; i = edge[i].next)
for (int j = path[b]; j != -; j = edge[j].next)
(ans += S.a[i][j^]) %= MOD;
printf("%d\n", ans);
}
int main() {
work();
return ;
}