首页 > 代码库 > 矩阵快速幂优化递推总结

矩阵快速幂优化递推总结

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}

矩阵快速幂优化递推总结