考虑这样一个问题
给定
阶矩阵
,求
。
矩阵幂求和?我会二分!其实二分也是也是一种不错的方法,不过还有一种方法。我们来分析一下。
二分法
对次数进行二分,递归求出次的答案,利用前
次答案求出后
次的答案,
奇数时需要一些处理。
时间复杂度。
构造矩阵法
矩阵的幂求和还能构造矩阵吗?先来看一个简化版的问题:
等比数列
,求下述数列的第
项,将答案
输出
对于这个问题,我们构造矩阵
将矩阵展开,有
现在我们可以解决矩阵版的问题了。矩阵的运算和整数的运算在许多方面是相像的,类似地,我们定义阶单位阵为
,
阶零矩阵为
,设
,则我们可以构造出
阶转移矩阵
在这样的转移中,,满足题意。
时间复杂度,常数略大,但较易理解。