矩阵快速幂可用来优化递推
矩阵快速幂的实现及一些详细介绍可以参考我的另一篇文章：
数论常用内容——矩阵快速幂
首先，需要先构造合适的初始状态（第一个矩阵）然后，利用此矩阵和矩阵乘法的性质，使用快速幂的手段求出之后的状态
构造矩阵可以根据矩阵乘法的实现特点来构造，利用合适的性质可以简化运算
例如：给出矩阵A，求S = A + A2 + A3 + … + Ak
复制代码
1
2
3
4
5
6
7
8
9
10分析：把问题转化以加速，令 B = A I 0 I 则B^(k + 1) = A^(k + 1) I + A + A2 + A3 + … + Ak 0 I
再比如，求fibnacci数列的时候用
1 1
0 1
作为首项再做n次方求fib（n）
最后
以上就是忧郁流沙最近收集整理的关于矩阵快速幂的应用——优化递推过程的全部内容，更多相关矩阵快速幂内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复