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

题解:

这题卡常啊,居然矩乘可以TLE.

本题大概思路如下:

这题因为有不能回走的要求,所以不能向平时那样直接对邻接矩阵做矩乘了,需要对边做矩乘,在矩阵中把自己和自己的位置设为0,这样可以保证不会往回走,并且注意要虚拟一个初始节点连向输入的S,最后统计答案直接将连到t的边的方案数相加即可

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int N=55,M=150;

int n,m,T,s,t,mod=45989,map[M][M],head[N],to[M],nxt[M],num=1;

void init(int x,int y){

    nxt[++num]=head[x];to[num]=y;head[x]=num;

}

struct mat{

    int a[M][M];

    mat(){}

    mat(int mp[M][M]){

        for(RG int i=1;i<=num;i++)

            for(RG int j=1;j<=num;j++)a[i][j]=mp[i][j];

    }

    mat operator *(const mat &p)const{

        mat tmp;

        for(RG int i=1;i<=num;i++)

            for(RG int j=1;j<=num;j++){

                tmp.a[i][j]=0;

                for(RG int k=1;k<=num;k++){

                    tmp.a[i][j]+=(a[i][k]*p.a[k][j])%mod;

                    if(tmp.a[i][j]>=mod)tmp.a[i][j]-=mod;

                }

            }

        return tmp;

    }

};

void work()

{

    scanf("%d%d%d%d%d",&n,&m,&T,&s,&t);

    s++;t++;T--;

    int x,y;

    for(int i=1;i<=m;i++){

        scanf("%d%d",&x,&y);

        x++;y++;

        init(x,y);init(y,x);

    }

    for(int i=head[s];i;i=nxt[i])

        map[1][i]++;

    for(int i=2;i<=num;i++){

        for(int j=head[to[i]];j;j=nxt[j])

            if(i!=(j^1))map[i][j]++;

    }

    mat S=mat(map),K=mat(map);

    while(T){

        if(T&1)S=S*K;

        K=K*K;T>>=1;

    }

    int ret=0;

    for(RG int i=2;i<=num;i++){

        if(to[i]==t){

            ret+=S.a[1][i];

            if(ret>=mod)ret-=mod;

        }

    }

    printf("%d\n",ret);

}

int main()

{

    work();

    return 0;

}