【BZOJ1875】【矩阵乘法】[SDOI2009]HH去散步

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

HINT

对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。
对于100%的数据，N ≤ 20，M ≤ 60，t ≤ 230，0 ≤ A,B<n，0 ≤="" ai,bi="" <n。<="" p="">

【分析】

这个，能算数学吧...（其实是DP）

简单的矩阵乘法，练下手。

 /*

 宋代朱敦儒

 《西江月·世事短如春梦》

 世事短如春梦，人情薄似秋云。不须计较苦劳心。万事原来有命。

 幸遇三杯酒好，况逢一朵花新。片时欢笑且相亲。明日阴晴未定。

 */

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <queue>

 #include <vector>

 #include <iostream>

 #include <string>

 #include <ctime>

 #define LOCAL

 const int MAXN =  *  + ;

 const int MOD = ;

 const double Pi = acos(-1.0);

 long long G = ;//原根

 const int MAXM =  *  + ;

 using namespace std;

 //读入优化

 void read(int &x){

     char ch;x = ;

     int flag = ;

     ch = getchar();

     while (ch < '' || ch > '') {if (ch == '') flag = -; ch = getchar();}

     while (ch >= '' && ch <= '') {x = x *  + (ch - ''); ch = getchar();}

     x *= flag;

 }

 struct Edge{

        int u, v;

 }edge[MAXM];

 int M;

 struct Matrix{

        int num[MAXN][MAXN];

        //Matrix(){memset(num, 0, sizeof(num));}

        Matrix operator * (const Matrix &b){

               Matrix c;

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

               for (int i = ; i < M; i++)

               for (int j = ; j < M; j++)

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

                   //if (i == 5 && j == 9)

                   //printf("");

                   c.num[i][j] = (c.num[i][j] + num[i][k] * b.num[k][j]) % MOD;

               }

               return c;

        }

 }x1, x2, x3;

 Matrix pow(Matrix a, int b){

        if (b == ) return a;

        Matrix tmp = pow(a, b / );

        if (b %  == ) return tmp * tmp;

        else return (tmp * tmp) * a;

 }

 int n, m, t, A, B, head[MAXN], next[MAXM];

 //无向边

 void addEdge(int u, int v){

      edge[M].u = u; edge[M].v = v;

      next[M] = head[u];

      head[u] = M++;

      edge[M].u = v; edge[M].v = u;

      next[M] = head[v];

      head[v] = M++;

 }

 void init(){

      memset(x1.num, , sizeof(x1.num));

      memset(x2.num, , sizeof(x2.num));

      memset(x3.num, , sizeof(x3.num));

      memset(head, -, sizeof(head));

      read(n);read(m);

      read(t);read(A);read(B);

      M = ;//注意这里要人为规定一个源

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

          int u, v;

          read(u);read(v);

          addEdge(u, v);

      }

 }

 void prepare(){

      for (int i = head[A]; i != -; i = next[i]) x1.num[][i]++;

      for (int i = ; i < M; i++)

      for (int j = ; j < M; j++)

      if (edge[i].v == edge[j].u && (i ^ ) != j) x2.num[i][j]++;//注意这里是以边来相连

 /*

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

          for (int j = 1; j < M ; j++) printf("%d ", x2.num[i][j]);

          printf("\n");

      }*/

 }

 void work(){

      int Ans = ;

      x1 = x1 * pow(x2, t - );

      /*for (int i = 1; i < M; i++){

          for (int j = 1; j < M ; j++) printf("%d ", x1.num[i][j]);

          printf("\n");

      }*/

      for (int i = head[B]; i != -; i = next[i]) Ans = (Ans + x1.num[][i ^ ]) % MOD;

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

 }

 int main(){

     init();

     prepare();

     work();

     return ;

 }

秒客网