[SDOI 2009]HH去散步-白红宇

[SDOI 2009]HH去散步

阅读量：4683 次

发布时间：2019-06-09

本文共 2527 字，大约阅读时间需要 8 分钟。

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

题解

我们将无向边拆成两条有向边，边点互换，就可以求出满足题意的解了。

1 //It is made by Awson on 2017.10.12 2 #include  3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 #include 
                  
                   15 #define LL long long16 #define Min(a, b) ((a) < (b) ? (a) : (b))17 #define Max(a, b) ((a) > (b) ? (a) : (b))18 #define Abs(x) ((x) < 0 ? (-(x)) : (x))19 using namespace std;20 const int MOD = 45989;21 22 int n, m, t, a, b, u, v;23 int f[125][125];24 struct tt {25 int to, next;26 }edge[125];27 int path[25], top = -1;28 struct mat {29 int a[125][125];30 mat () {31 memset(a, 0, sizeof(a));32 }33 mat (int _a[125][125]) {34 for (int i = 0; i <= top; i++)35 for (int j = 0; j <= top; j++)36 a[i][j] = _a[i][j];37 }38 mat operator * (const mat &b) const{39 mat ans;40 for (int i = 0; i <= top; i++)41 for (int j = 0; j <= top; j++)42 for (int k = 0; k <= top; k++) 43 (ans.a[i][j] += a[i][k]*b.a[k][j]) %= MOD;44 return ans;45 }46 }S, T;47 48 void add(int u, int v) {49 edge[++top].to = v;50 edge[top].next = path[u];51 path[u] = top;52 }53 void work() {54 memset(path, -1, sizeof(path));55 scanf("%d%d%d%d%d", &n, &m, &t, &a, &b);56 for (int i = 1; i <= m; i++) {57 scanf("%d%d", &u, &v);58 add(u, v), add(v, u);59 }60 if (t == 1) {61 int ans = 0;62 for (int i = path[a]; i != -1; i = edge[i].next)63 ans += edge[i].to == 1;64 printf("%d\n", ans);65 return;66 }67 for (int i = 0; i <= top; i++)68 for (int j = path[edge[i].to]; j != -1; j = edge[j].next)69 if (i != (j^1)) f[i][j]++;70 S = mat(f), T = mat(f);71 t -= 2;72 while (t) {73 if (t&1) S = S*T;74 t >>= 1;75 T = T*T;76 }77 int ans = 0;78 for (int i = path[a]; i != -1; i = edge[i].next)79 for (int j = path[b]; j != -1; j = edge[j].next)80 (ans += S.a[i][j^1]) %= MOD;81 printf("%d\n", ans);82 }83 int main() {84 work();85 return 0;86 }