HDU 2157 How many ways?? (邻接矩阵快速幂)

http://acm.hdu.edu.cn/showproblem.php?pid=2157

题意 : 给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值

从这道题才知道邻接矩阵竟然可以乘 , 惊了 ! ! ! 矩阵真的不是白叫的 .

虽然很容易推出是可行的但是还是觉得很神奇 .

WA了几百次 , 后来发现是快速幂的问题 , 我还是不知道为什么 ,

我之前的快速幂因为不想初始化z都直接在第一次乘的时候特殊判断直接把x赋给z , 也没有出现问题 , 但是既然错了...就这样写吧 , 记住就好了 .

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 using namespace std;
 8 const int maxn=110;
 9 const double eps=1e-8;
10 const long long modn=1000;
11 int n,m;
12 struct mat{
13     int e[31][31];
14     mat(){
15         memset(e,0,sizeof(e));
16     }
17 };
18 mat pro(mat x,mat y){
19     mat z;
20     for(int i=1;i<=n;i++){
21         for(int j=1;j<=n;j++){
22             for(int k=1;k<=n;k++){
23                 z.e[i][j]+=x.e[i][k]*y.e[k][j];
24                 z.e[i][j]%=1000;
25             }
26         }
27     }return z;
28 }
29 mat pow(mat x,int k){
30     mat z;
31     for(int i=1;i<=n;i++){
32         z.e[i][i]=1;
33     }
34     while(k){
35         if(k%2==1){
36             z=pro(z,x);
37         }
38         x=pro(x,x);
39         k/=2;
40     }
41     return z;
42 }
43 int main(){
44     while(~scanf("%d%d",&n,&m)&&(m||n)){
45         mat a;
46         mat c;
47         int x,y,k;
48         for(int i=1;i<=m;i++){
49             scanf("%d%d",&x,&y);
50             a.e[x+1][y+1]=1;
51         }
52         scanf("%d",&m);
53         for(int i=1;i<=m;i++){
54             scanf("%d%d%d",&x,&y,&k);
55             c=a;
56             c=pow(a,k);
57             int ans=c.e[x+1][y+1]%1000;
58             printf("%d
",ans);
59         }
60     }
61     return 0;
62 }

View Code

HDU 2157 How many ways?? (邻接矩阵快速幂)

相关推荐