hdu 2157 How many ways?? (矩阵快速幂经典题目)

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

思路:
 把给定的图转为邻接矩阵,即A(i,j)=1当且仅当存在一条边i->j。令C=A*A,那么C(i,j)=ΣA(i,k)*A(k,j),实际上就等于从点i到点j恰好经过2条边的路径数(枚举k为中转点)。类似地,C*A的第i行第j列就表示从i到j经过3条边的路径数。同理,如果要求经过k步的路径数,我们只需要快速幂求出A^k即可。

M67_十个利用矩阵乘法解决的经典题目

这个转化好美啊。。。

 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz