2017 Wuhan University Programming Contest (Online Round) Lost in WHU 矩阵快速幂 一个无向图，求从1出发到达n最多经过T条边的方法数，边可以重复经过，到达n之后不可以再离开。

/**

题目：Lost in WHU

链接：https://oj.ejq.me/problem/26

题意:一个无向图，求从1出发到达n最多经过T条边的方法数，边可以重复经过，到达n之后不可以再离开。

思路：一个邻接矩阵（01矩阵）自身的T次方那么，a[i][j]的结果表示i到j经过T条边的方法数。（通过矩阵相乘理解

c.m[i][j] = (c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod; 表示i到j，通过i先到k，然后k到j；）

那么求a[1][n]的T步就是T个a矩阵相乘；

由于本题是T以内的方法数。那么通过对矩阵相乘的理解，可以想到增加一个n到达n的边。这时候保证T个矩阵相乘的过程中，当前已经获得的矩阵c

乘以一个a矩阵后，可以保证原先的c[1][n]方法数累加进去。即:c.m[1][n]*a.m[n][n];

然后用快速幂加速矩阵相乘即可。

*/

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int maxn = 1e2+;

const int mod = 1e9+;

int n, m, k;

struct mat

{

    ll m[maxn][maxn];

    mat operator*(const  mat &b){

        mat c, a = *this;

        memset(c.m, , sizeof c.m);

        for(int i = ; i <= n; i++){

            for(int j = ; j <= n; j++){

                for(int k = ; k <= n; k++){

                    c.m[i][j] = (c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod;

                }

            }

        }

        return c;

    }

    mat operator^(int y){

        mat x = *this;

        mat p;

        memset(p.m, , sizeof p.m);

        for(int i = ; i <= n; i++){

             p.m[i][i] = ;

        }

        while(y>){

           if(y&) p = p*x;

           x = x*x;

           y >>= ;

        }

        return p;

    }

} x;

/*

ll solve(int y)

{

   mat p;

   memset(p.m, 0, sizeof p.m);

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

        p.m[i][i] = 1;

   }

   while(y>0){

      if(y&1) p = p*x;

      x = x*x;

      y >>= 1;

   }

   return p.m[1][n];

}*/

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        int u, v;

        memset(x.m, , sizeof x.m);

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

            scanf("%d%d",&u,&v);

            x.m[u][v] = x.m[v][u] = ;

        }

        for(int i = ; i < n; i++) x.m[n][i] = ;///到达终点后不可以再出去，除非去自身。

        x.m[n][n] = ;

        scanf("%d",&k);

        //printf("%lld\n",solve(k));

        mat ans = x^k;

        printf("%lld\n",ans.m[][n]);

    }

    return ;

}

2017 Wuhan University Programming Contest (Online Round) Lost in WHU 矩阵快速幂 一个无向图，求从1出发到达n最多经过T条边的方法数，边可以重复经过，到达n之后不可以再离开。的相关教程结束。