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

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

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

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

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

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

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

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 using namespace std;

 const int maxn=;

 const double eps=1e-;

 const long long modn=;

 int n,m;

 struct mat{

     int e[][];

     mat(){

         memset(e,,sizeof(e));

     }

 };

 mat pro(mat x,mat y){

     mat z;

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

         for(int j=;j<=n;j++){

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

                 z.e[i][j]+=x.e[i][k]*y.e[k][j];

                 z.e[i][j]%=;

             }

         }

     }return z;

 }

 mat pow(mat x,int k){

     mat z;

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

         z.e[i][i]=;

     }

     while(k){

         if(k%==){

             z=pro(z,x);

         }

         x=pro(x,x);

         k/=;

     }

     return z;

 }

 int main(){

     while(~scanf("%d%d",&n,&m)&&(m||n)){

         mat a;

         mat c;

         int x,y,k;

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

             scanf("%d%d",&x,&y);

             a.e[x+][y+]=;

         }

         scanf("%d",&m);

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

             scanf("%d%d%d",&x,&y,&k);

             c=a;

             c=pow(a,k);

             int ans=c.e[x+][y+]%;

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

         }

     }

     return ;

 }

巴特西

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

最新文章

热门文章