【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）

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

  1 /*
  2 宋代朱敦儒
  3 《西江月·世事短如春梦》
  4 世事短如春梦，人情薄似秋云。不须计较苦劳心。万事原来有命。
  5 幸遇三杯酒好，况逢一朵花新。片时欢笑且相亲。明日阴晴未定。 
  6 */
  7 #include <cstdio>
  8 #include <cstring>
  9 #include <algorithm>
 10 #include <cmath>
 11 #include <queue>
 12 #include <vector>
 13 #include <iostream>
 14 #include <string>
 15 #include <ctime>
 16 #define LOCAL
 17 const int MAXN = 60 * 2 + 10;
 18 const int MOD = 45989;
 19 const double Pi = acos(-1.0);
 20 long long G = 15;//原根 
 21 const int MAXM = 60 * 2 + 10; 
 22 using namespace std;
 23 //读入优化 
 24 void read(int &x){
 25     char ch;x = 0;
 26     int flag = 1;
 27     ch = getchar();
 28     while (ch < '0' || ch > '9') {if (ch == '0') flag = -1; ch = getchar();}
 29     while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0'); ch = getchar();}
 30     x *= flag;
 31 }
 32 
 33 struct Edge{
 34        int u, v;
 35 }edge[MAXM];
 36 int M;
 37 struct Matrix{
 38        int num[MAXN][MAXN];
 39        //Matrix(){memset(num, 0, sizeof(num));}
 40        Matrix operator * (const Matrix &b){
 41               Matrix c;
 42               memset(c.num, 0, sizeof(c.num));
 43               for (int i = 1; i < M; i++)
 44               for (int j = 1; j < M; j++)
 45               for (int k = 1; k < M; k++){
 46                   //if (i == 5 && j == 9)
 47                   //printf("");
 48                   c.num[i][j] = (c.num[i][j] + num[i][k] * b.num[k][j]) % MOD;
 49               }
 50               return c;
 51        }
 52 }x1, x2, x3;
 53 Matrix pow(Matrix a, int b){
 54        if (b == 1) return a;
 55        Matrix tmp = pow(a, b / 2);
 56        if (b % 2 == 0) return tmp * tmp;
 57        else return (tmp * tmp) * a; 
 58 }
 59 int n, m, t, A, B, head[MAXN], next[MAXM];
 60 
 61 //无向边 
 62 void addEdge(int u, int v){
 63      edge[M].u = u; edge[M].v = v;
 64      next[M] = head[u];
 65      head[u] = M++;
 66      
 67      edge[M].u = v; edge[M].v = u;
 68      next[M] = head[v];
 69      head[v] = M++;
 70 }
 71 void init(){
 72      memset(x1.num, 0, sizeof(x1.num));
 73      memset(x2.num, 0, sizeof(x2.num));
 74      memset(x3.num, 0, sizeof(x3.num));
 75      memset(head, -1, sizeof(head));
 76      read(n);read(m);
 77      read(t);read(A);read(B);
 78      M = 2;//注意这里要人为规定一个源 
 79      for (int i = 1; i <= m; i++){
 80          int u, v;
 81          read(u);read(v);
 82          addEdge(u, v);
 83      }
 84 } 
 85 void prepare(){
 86      for (int i = head[A]; i != -1; i = next[i]) x1.num[1][i]++;
 87      
 88      for (int i = 2; i < M; i++)
 89      for (int j = 2; j < M; j++)
 90      if (edge[i].v == edge[j].u && (i ^ 1) != j) x2.num[i][j]++;//注意这里是以边来相连 
 91 /*
 92      for (int i = 1; i < M; i++){
 93          for (int j = 1; j < M ; j++) printf("%d ", x2.num[i][j]);
 94          printf("
");
 95      }*/
 96 }
 97 void work(){
 98      int Ans = 0;
 99      x1 = x1 * pow(x2, t - 1); 
100      /*for (int i = 1; i < M; i++){
101          for (int j = 1; j < M ; j++) printf("%d ", x1.num[i][j]);
102          printf("
");
103      }*/
104      for (int i = head[B]; i != -1; i = next[i]) Ans = (Ans + x1.num[1][i ^ 1]) % MOD;
105      printf("%d
", Ans); 
106 }
107 
108 int main(){
109     init();
110     prepare();
111     work();
112     return 0;
113 }

View Code