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
0 1
0 2
0 3
2 1
3 2
Sample Output
HINT
对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。 对于100%的数据，N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B
Source
Day1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
矩阵乘法优化DP~
因为还要判重，所以矩阵记录的是边而不是点。
矩阵tot记录DP，初始时把所有两两可达的边的a[i][j]值+1，然后tot=tot^(t-1)，做t-1次乘法。
但是题目要求从a到b，所以再记录bas矩阵，把所有与a相连的边a[0][i]标记为1，再与tot相乘，筛去所有起点不是a的路径。
最后，记录所有最终边与b相连的路径条数，输出即可~
注意有重边，可以走过去再从重边走回来，所以判断的时候要按边的编号来判断是否是一条边，不能直接按点判断。
（对于一条边i，它的相反边是i+((i&1) ? 1:-1)。）
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define modd 45989int n,m,t,a,b,x,y,fi[21],ne[121],w[121],fro[121],cnt,ans;struct node{int a[121][121];
}bas,tot;void add(int u,int v)
{w[++cnt]=v;ne[cnt]=fi[u];fi[u]=cnt;fro[cnt]=u;w[++cnt]=u;ne[cnt]=fi[v];fi[v]=cnt;fro[cnt]=v;
}node operator * (node u,node v)
{node z;for(int i=0;i<=m*2;i++)for(int j=0;j<=m*2;j++){z.a[i][j]=0;for(int k=0;k<=m*2;k++) z.a[i][j]+=(u.a[i][k]*v.a[k][j])%modd,z.a[i][j]%=modd;}return z;
}node operator ^ (node u,int v)
{node z;for(int i=0;i<=m*2;i++) z.a[i][i]=1;while(v){if(v&1) z=z*u;v>>=1;u=u*u;}return z;
}int main()
{scanf("%d%d%d%d%d",&n,&m,&t,&a,&b);a++;b++;memset(fi,-1,sizeof(fi));for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);x++;y++;add(x,y);}for(int i=fi[a];i!=-1;i=ne[i]) bas.a[0][i]++;for(int i=1;i<=cnt;i++){x=fro[i],y=w[i];for(int j=fi[y];j!=-1;j=ne[j])if(j!=i+((i&1) ? 1:-1)) tot.a[i][j]++;}tot=tot^(t-1);bas=bas*tot;for(int i=1;i<=cnt;i++)if(w[i]==b) ans=(ans+bas.a[0][i])%modd;printf("%d\n",ans);return 0;
}