矩阵与递推
课件： 矩阵与递推 矩阵在第二个月就学过，递推就更早。 当时教练说矩阵可以 加速递推 ，但是我弱，当时并不知道怎么加速。 直到上个月我才在厕所里脑补出来矩阵如何加速递推…… 由于概念在课件中讲得很详细，我们来探讨一下 如何推出对应的矩阵 吧。 我们需要构造： [ F n , F n + 1 ] [ F n , F n + 1 ] 乘上某个东西，得到之后的斐波那契数。 我们应该如何构造矩阵乘法的结果呢？显然这个东西 必须循环 ，也就是变成 [ F k , F k + 1 ] [ F k , F k + 1 ] 的格式，来方便我们快速幂。 那么大体的思路就是： [ F n , F n + 1 ] × s t h . = [ F n + 1 , F n + 2 ] [ F n , F n + 1 ] × s t h . = [ F n + 1 , F n + 2 ] 。 首先我们发现， F n + 1 F n + 1 必须保留下来。那么矩阵一定要留出一列来把 F n + 1 F n + 1 照抄。所以矩阵就是： [ 0 x 1 y ] [ 0 x 1 y ] 。 由于斐波那契数列的性质，构造 F n + 2 F n + 2 需要 F n + F n + 1 F n + F n + 1 ，所以 x = 1 , y = 1 x = 1 , y = 1 。这样补上之后，我们得到一个矩阵乘法： [ F n F n + 1 ] [ 0 1 1 1 ] = [ F n + 1 F n + 2 ] [ F n F n + 1 ] [ 0 1 1 1 ] = [ F n + 1 F n + 2 ] 然后就可以快速幂了。 总结一下思路： 1.先构造起始矩阵和目标矩阵。 2.确定乘数矩阵。 3.快速幂。 然后问题就解决了。 一个递推如果要用矩阵来加速，应该满足 后项可以由前项唯一确定 。同时构造的矩阵要 尽量小 ，以免在矩阵乘法上浪费过多的时间。 blue 矩阵与递推 斐波那契数列 已知： 푎 1 = 푎 2 = ꢀ 푎 푖 = 푎 푖−1 ...