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
Sample Output
4
HINT
对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。
对于100%的数据，N ≤ 20，M ≤ 60，t ≤ 230，0 ≤ A,B
分析：
第一次写矩阵优化这样的递推式
（以前都是f[i]=x*f[i-1]+y*f[i-2]+…这种单纯不做作的递推式）
现在才知道，只要是当前状态从几个固定的状态转移，都可以矩阵优化
本题唯一特殊的一点就是：
不能沿着刚刚走来的路走回，
注意：不是不能走重边，而是不能反向走刚刚走过的边
正常的方法构造点的转移不能避免这个问题，就用边来构造
只要保证不经过自己的反向边就可以保证不走回头路了
这样的话矩阵就不能用点来构造了
要用边来构造
将两条有向边按是否首尾相接建立邻接矩阵
所有边way[i]:u->v与way[j]:v->w (j不是i的反向边)，都有H[i][j]=1
此时H[i][j]=1的意义是:从边i的末端走一步能到达边j的末端，有1种方案
把H[i][i的反向边]设成0，
这样就避免了”沿着刚刚走来的路走回”的情况
只需将这个矩阵自乘t-1次
又因为起点规定好是A，再构造一个系数矩阵X，
使其与H相乘后仅保留H[i][j]中i的起点是A的位置，累加终点是B的边j的答案即可
tip
在判断是不是反向边并构造H的时候
我一开始写的判断是 way[j].y!=way[i].x
就玄学的WA了将近一小时
后来改成
j!=fan(i)
就A了
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
const int mod=45989;
const int N=125;
struct node{
int H[N][N];
node operator *(const node &a) const
{
node ans;
for (int i=1;i<N;i++) //
for (int j=1;j<N;j++)
{
ans.H[i][j]=0;
for (int k=1;k<N;k++)
ans.H[i][j]=(ans.H[i][j]+H[i][k]*a.H[k][j]%mod)%mod;
}
return ans;
}
void clear()
{
memset(H,0,sizeof(H));
}
node KSM(int p)
{
p--;
node ans=(*this),a=(*this);
while (p)
{
if (p&1)
ans=ans*a;
a=a*a;
p>>=1;
}
return ans;
}
};
node h,X;
int n,m,t,A,B,st[101],tot=0,S;
struct node1{
int x,y,nxt;
};
node1 way[303];
void add(int u,int w)
{
tot++;
way[tot].x=u;way[tot].y=w;way[tot].nxt=st[u];st[u]=tot;
tot++;
way[tot].x=w;way[tot].y=u;way[tot].nxt=st[w];st[w]=tot;
}
int fan(int bh) //求反向边
{
if (bh&1) return bh+1;
else return bh-1;
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&t,&A,&B);
for (int i=1;i<=m;i++)
{
int u,w;
scanf("%d%d",&u,&w);
add(u,w);
}
if (t==0)
{
if (A==B) printf("1");
else printf("0");
}
else
{
for (int i=st[A];i;i=way[i].nxt)
X.H[1][i]=1; //构造系数矩阵，只有从A出发的边才算数
if (t>1)
{
for (int i=1;i<=tot;i++)
{
int r=way[i].y;
for (int j=st[r];j;j=way[j].nxt)
if (j!=fan(i)) h.H[i][j]=1; //从边i的末端走一步能到达边j的末端
}
node ans=h.KSM(t-1);
X=X*ans; //与系数矩阵相乘
}
int tt=0;
for (int i=st[B];i;i=way[i].nxt)
tt+=X.H[1][fan(i)]; ///tt%=mod;
printf("%d",tt%mod);
}
return 0;
}