首页 > 代码库 > 矩阵乘法的应用
矩阵乘法的应用
我们都知道矩阵可以用来很方便的求多个方程组,但矩阵的作用不单单只用来求方程组。下面记录一下本人对矩阵应用的一点点了解,还有很多应用看不懂,以后看懂了会在此处慢慢更新。
1.化简递推类问题。
比如,我们现在要求第N项Fiboncci值模上一个p的结果是多少?
2.给定一个有向图,问从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条边或2个结点的路径数(枚举k为中转点)。类似地,C*A的第i行第j列就表示从i到j经过3条边的路径数。同理,如果要求经过k步的路径数,我们只需要二分求出A^k即可。
矩阵乘法的应用
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。