首页 > 代码库 > 矩阵快速幂优化递推总结
矩阵快速幂优化递推总结
RT,主要总结一下矩阵的求法。
首先能用矩阵快速幂优化的递推类型是f[n]=5f[n-3]+6f[n-2]+2f[n-1]+n^2+n+8之类的
也就是说递推是线性递推且f[n-i]前面的系数是常数,可以含有与n有关的多项式,也可以含有常数的这种递推,下面总结一下矩阵的写法:
先考虑最简单的常数,我们其实可以忽略常数,因为顶多在没有常数的矩阵外面加一行一列就行了
以f[n]=2f[n-1]+6f[n-2]+5f[n-3]+n^2+n为例
先写迭代的矩阵,一般可以写成一行,右边有几项写几项
{f[n-1],f[n-2],f[n-3],n^2,n}
如果这么写的话,那肯定数字矩阵是5*5的(因为1*5矩阵乘5*x矩阵等于1*5矩阵,那么肯定x=5)
不过发现这样不行,为什么呢?因为n^2和n不能通过简单的数字的四则运算得到(n+1)^2和n+1,但我们可以这样写
{f[n-1],f[n-2],f[n-3],n^2,n,2n,1,1}
*
2 1 0 0 0 0 0 0
6 0 1 0 0 0 0 0
5 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 0 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 1 0 0 1 0
0 0 0 0 1 2 0 1
={f[n],f[n-1],f[n-2],(n+1)^2,n+1,2(n+1),1,1}
怎么想到的呢??从n^2->(n+1)^2和n->n+1入手,(n+1)^2-n^2=2n+1,所以便有了后面的2n项和1项,n+1-n=1,所以便有了后面的1项。(其实多出的2n也要考虑,只不过有了1项,所以就融入在里面了。)
当然以上的不是最简单的,还可以化简,不过这是一种构造方法啦= =
——————————————————————————————————————
考虑加上常数8,就轻轻松松写出:
{f[n-1],f[n-2],f[n-3],n^2,n,2n,1,1,8}
*
2 1 0 0 0 0 0 0 0
6 0 1 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0
1 0 0 0 1 0 0 0 0
0 0 0 1 0 1 0 0 0
0 0 0 1 0 0 1 0 0
0 0 0 0 1 2 0 1 0
0 0 0 0 0 0 0 0 1
={f[n],f[n-1],f[n-2],(n+1)^2,n+1,2(n+1),1,1,8}
矩阵快速幂优化递推总结