flag
title: 矩阵快速幂 date: 2017/9/18 07:46:25 categories: - OI tags: - OI - 数学 - 矩阵运算 - COGS ---矩阵快速幂.md

前置技能

矩阵乘法

复杂度为$O(n^3)$,有复杂度稍低的分治写法,不过意义不大(毕竟你的矩阵这么小)

$A,B$是两个矩阵,其中$A$是$m\times n$的矩阵,$B$是$x\times y$的矩阵

当且仅当$n=x$时$A\cdot B$有意义。

注意:矩阵乘法不满足交换律,设$C=A\cdot B$,则

一般的,我们用矩阵去左乘一个向量,来对该向量进行线性变换

如果对于矩阵乘法仅仅是会写代码的程度,请深入理解并能够手算,否则不要阅读以下内容。

快速幂

复杂度$O(\log n)$

这个没啥好说的,如果不会可以上网搜或者看我之前的博客

矩阵快速幂

矩阵加上快速幂,可以迅速求出线性递推式的第$n$项,或者是前$n$项和(必须是线性组合

求斐波那契数列

斐波那契数列的定义:

我们注意到,该数列的第$n$项是第$n-1$项和第$n-2$项的线性组合(你tm在放屁

我们构造一个列向量:

然后我们考虑第$n+1$项,是第$n$项和第$n-1$项的线性组合(简直是废话

同样的,我们也可以构造一个列向量:

然后我们考虑一下怎么把$A$经过一波骚变换而把它变成$B$,由于这是向量之间线性组合,左乘一个矩阵是可以的:

嗯,就这样变换。

如果我要求第$n$项,就再左乘$n-2$个同样的矩阵,所以,我们有:

然后左边的那个矩阵的幂可以用快速幂处理,可以在$O(\log n)$时间内求出,再乘一下那个列向量,就得到了我们要求的东西。

进阶版:求两项的线性递推式

题目:COGS

其实就是给斐波那契数列加上了系数。

矩阵会变成这样:

极限版:求n项的线性递推式

题目:COGS

嗯。。。这个就比较毒瘤了。。。


还是要构造矩阵。。(怕是要敲公式敲死)

还是去网上搜一个矩阵粘下来吧(懒癌爆发)

好像并没有人手敲矩阵。。决定吃螃蟹。。。


其中$a_1,a_2,\cdots a_n$和$f(1),f(2),\cdots f(n)$已知。

大力构造矩阵:(md真丑)

啊。。我尽力了。。。就是这样。。敲公式真累。。。

求斐波那契数列的前n项和

即求

这个和之前的还是不太一样的,没有明确的递推式。

我们注意到前$n$项和$sum_n$是$sum_{n-1}$和$F_n$的线性组合,然后构造矩阵:

求自然数列的前n项平方和

即求:

由于$sum_{n+1}$是$sum_n$与$(i+1)^2$的线性组合,$(i+1)^2$是$i^2,\ i,\ 1$的线性组合,因此可以构造矩阵:

求斐波那契数列的前n项平方和

即求

注意到$sum_n$是$F_n^2$与$sum_{n-1}$的线性组合,而$F_n^2$是$F_{n-1}^2$和$F_{n-2}^2$和$F_{n-1}F_{n-2}$的线性组合,所以构造矩阵:

注意在推矩阵的最后以后时使用了一些骚操作,可以手推一下验证一下正确性

求自然数列的前n项立方和

即求:

注意到$sum_{n+1}$是$(i+1)^3$与$sum_{n}$的线性组合,而$(i+1)^3=i^3+3i^2+3i+1$,是$i^3,i^2,i,1$的线性组合,$(i+1)^2=i^2+2i+1$,是$i^2$与$i$的线性组合,$i+1$是$i$与$1$的线性组合,因此构造矩阵:

参考资料

写在最后

本文中举出的一些例子有更简单的做法,比如后三个,之所以以最复杂的形式展示出来,是为了提高构造矩阵的能力。还有,敲公式真tm累

navigate_before