HDU----(2157)How many ways??(快速矩阵幂)
How many ways??
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1562 Accepted Submission(s): 546
Problem Description
春 天到了, HDU校园里开满了花, 姹紫嫣红, 非常美丽. 葱头是个爱花的人, 看着校花校草竞相开放, 漫步校园, 心情也变得舒畅. 为了多看看这迷人的校园, 葱头决定, 每次上课都走不同的路线去教室, 但是由于时间问题, 每次只能经过k个地方, 比方说, 这次葱头决定经过2个地方, 那他可以先去问鼎广场看看喷泉, 再去教室, 也可以先到体育场跑几圈, 再到教室. 他非常想知道, 从A 点恰好经过k个点到达B点的方案数, 当然这个数有可能非常大, 所以你只要输出它模上1000的余数就可以了. 你能帮帮他么?? 你可决定了葱头一天能看多少校花哦
Input
输 入数据有多组, 每组的第一行是2个整数 n, m(0 < n <= 20, m <= 100) 表示校园内共有n个点, 为了方便起见, 点从0到n-1编号,接着有m行, 每行有两个整数 s, t (0<=s,t<n) 表示从s点能到t点, 注意图是有向的.接着的一行是两个整数T,表示有T组询问(1<=T<=100), 接下来的T行, 每行有三个整数 A, B, k, 表示问你从A 点到 B点恰好经过k个点的方案数 (k < 20), 可以走重复边。如果不存在这样的走法, 则输出0 当n, m都为0的时候输入结束
Output
计算每次询问的方案数, 由于走法很多, 输出其对1000取模的结果
Sample Input
4 4 0 1 0 2 1 3 2 3 2 0 3 2 0 3 3 3 6 0 1 1 0 0 2 2 0 1 2 2 1 2 1 2 1 0 1 3 0 0
Sample Output
2 0 1 3
Author
小黑
Source
对于这道题，不能不说构思确实很精妙，之前学的线性代数，居然没有注意这一点，╮(╯▽╰)╭。每一次都会从一个点遍历到所有的点，然后将其可能性累加，这不就是矩阵的特性吗，╮(╯▽╰)╭。
好了，做法其实还是很单纯的，只是如果没有想到的话，估计很难做出来。构造一个邻接矩阵，对应的点如果能联通就涂1，这样就完美的转化为一个矩阵。对于每一次进行一次矩阵求解即可。O(∩_∩)O哈哈~
代码： 105ms c++
1 //#define LOCAL
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5 using namespace std;
6 int mat[21][21];
7 int ans[21][21];
8 int sav[21][21];
9 int n,m,t;
10 void init(int ans[][21])
11 {
12 for(int i=0;i<n;i++)
13 {
14 for(int j=0;j<n;j++)
15 {
16 if(i==j) ans[i][j]=1;
17 else ans[i][j]=0;
18 }
19 }
20 }
21
22 void Matrix(int a[][21],int b[][21])
23 {
24 int cc[21][21]={0};
25 for(int i=0;i<n;i++)
26 {
27 for(int j=0;j<n;j++)
28 {
29 for(int k=0;k<n;k++)
30 {
31 cc[i][j]=(cc[i][j]+a[i][k]*b[k][j])%1000;
32 }
33 }
34 }
35 for(int i=0;i<n;i++)
36 {
37 for(int j=0;j<n;j++)
38 {
39 a[i][j]=cc[i][j];
40 }
41 }
42 }
43
44 void pow(int w)
45 {
46 while(w>0)
47 {
48 if(w&1) Matrix(ans,mat);
49 w>>=1;
50 if(w==0)break;
51 Matrix(mat,mat);
52 }
53 }
54
55 void input()
56 {
57 int a,b,k;
58 memset(sav,0,sizeof(sav));
59 while(m--){
60 scanf("%d%d",&a,&b);
61 sav[a][b]=1;
62 }
63 scanf("%d",&t);
64 while(t--){
65 scanf("%d%d%d",&a,&b,&k);
66 for(int i=0;i<n;i++)
67 {
68 for(int j=0;j<n;j++)
69 mat[i][j]=sav[i][j];
70 }
71 init(ans);
72 pow(k);
73 printf("%d\n",ans[a][b]);
74 }
75 }
76
77 int main()
78 {
79 #ifdef LOCAL
80 freopen("test.in","r",stdin);
81 #endif
82 while(~scanf("%d%d",&n,&m)&&n+m!=0)
83 input();
84 return 0;
85 }