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;
}

#include <bits/stdc++.h>
#define P 45989
using namespace std;
const int N=125;
int n,m,k,s,t,p,tot,fi,ed,num,b[N];
vector<pair<int,int>> e[N];
struct Matrix{
	int a[N][N];
	Matrix(){ memset(a,0,sizeof(a));}//构造函数，矩阵初始化全零 
	Matrix operator*(Matrix &b)const{//重载乘法运算 
		Matrix tmp;
		for (int k=0;k<tot;++k)
			for (int i=0;i<tot;++i)
				for (int j=0;j<tot;++j)
					(tmp.a[i][j]+=a[i][k]*b.a[k][j])%=P;
		return tmp;
	}
}A,B;
void qpow(int p){
	for (int i=0;i<tot;++i) B.a[i][i]=1;
	for (;p;p>>=1){
		if (p&1) B=B*A;
		A=A*A;
	}
}
int main(){
	cin>>n>>m>>p>>fi>>ed;
	for (int i=1;i<=m;++i){
		cin>>s>>t;
		e[s].push_back({t,tot++});
		e[t].push_back({s,tot++});
	}	
	for (int u=0;u<n;++u)
		for (auto &i:e[u]){
			int v=i.first,id=i.second;
			if (v==ed) {//是终点，记录一下，最后需要统计答案 
				b[++num]=id;
			}
			for (auto &i:e[v]){//枚举从v出发的边 
				int ID=i.second;
				if ((id^1)!=ID) A.a[id][ID]=1;//不是走回来的边 
			} 
		}
	qpow(p-1);
	int ans=0;
	for (auto &i:e[fi]){//枚举起始边 
		int id=i.second;
		for (int j=1;j<=num;++j)//枚举结束边 
			ans=(ans+B.a[id][b[j]])%P;
	}
	cout<<ans;
}