矩阵加速线性递推式(转载)

Posted by 111qqz on Monday, October 17, 2016

TOC

找到了篇四年前空间中的旧文,也是有点感动2333.

快速求解多项递推式

问题描述:

已知 F(n) = AF(n-1) + BF(n-2) + CF(n-3)+…..

求解 F(n)%P

分析:

*************************************

如果n的值不大,一般来说在1000000之内,则可以考虑直接递推求解,只要预先花O(n)时间复杂度,可打出一张表,运行时直接查表就可以了.

另一方面,如果n值可能很大,如10^9,用这种方法无论是在内存还是时间上开销都太大,根本无法满足.本文将介绍一种与矩阵相关的高效通用算法.

举个例子:

*************************************

如果我们已知一个序列的前两项为a0,a1,递推关系为:F(n) = AF(n-1)+BF(n-2)

令矩阵 M = | 0   1 |         M(1) = | a0 |

| B A |                     | a1 |

N = M * M(1) =   |    a1           |

| Aa1+Ba0 |

而 Aa1+Ba0 刚好就是 a2 !

设     M(n) =    |   a(n-1) |

|    an     |

N = M * M(n) =     |    an              |

| Aan+Ba(n-1)|

很显然, Aan+Ba(n-1) 就是 a(n+1)

矩阵M(n)的第二个元素对应F(n),只要在前一个矩阵基础上左乘一个矩阵M就可以得到下一项F(n+1).这样把递推转化成了矩阵的乘法运算.

M^(n-1)*M1 =      |   F(n-1) |

|    F(n)   |

因此该问题就转化成了求解一个矩阵的n次方.

*************************************

同理,对于一个涉及三项的递推式F(n) = AF(n-1)+BF(n-2)+CF(n-3)

只要令  M =       | 0   1   0 |         M(1) =  | a0 |

| 0    0 1 |                       | a1 |

| C   B A |                      | a2 |

推导过程和上面类似,可以自己推导一下,也会得到如下的结论:

M^(n-1)*M1 =         |   F(n-1) |

|    F(n)    |

|    F(n+1) |

同样将问题转化成了解一个矩阵的n次方.

*************************************

一般化:

M 阵的建立:若一共有 m 个递推式,则建一个m行m列的矩阵,让第m行从右到左依次是递推项的系数A,B,C…..,在除第一列和最后一行的剩余矩阵的主对角线上写1,其余所有的都写0.

M(1)   阵的建立:该矩阵是 m 行一列阵,其值分别为F(0),F(1)…F(m-1)

结论的形式和上面的结论都差不多.

为什么要这样设定 M 和 M(1), 设定M(1)很好理解,关键是M, 只要你把两个矩阵乘起来,你就会发现其中的奥妙所在.

*************************************

要求一个矩阵的n次方,线性代数里面有相应的方法.

很实用的一个算法是二进制扫描法.(刘汝佳<算法艺术与信息学竞赛>P224)

总的时间复杂度约为O(log2(n))

这样一个很大的数n也能在很短的时间内算出来.

*************************************

二进制扫描法:

1.将n转化为二进制 n = bjb(j-1)…b2b1b0 bi = 0或1

2.M^2 = M*M   M^4 = (M^2)^2

这样可以得到 M 的1,2,4,8…2^32次方记为,M0,M1,M2,M3..M32.

3.M^n = (bjMj)(b(j-1)M(j-1))(b2M2)(b1M1)(b0M0)

若bi=1,则乘Mj;bj=0,则不乘

因为有 M^(a+b) = M^a*M^b

例:n = 9 = 1001(2) = 1000+0+0+1(2)

M^9 = M^(1000+0+0+1) = M^1000*M^1

= M3*M0

4.模运算有这样的性质: (ab)%c = [(a%c)(b%c)]%c

*************************************

练习:

SOJ:   cs.scu.edu.cn/soj

2984 Fibonacci

2385 Fibonacci Problem Again

2129 Sequence

1826 Number Sequence

3083 windy's cake III(只用到了二进制扫描法)

  阿宽补充:tyvj p1947 p1155 

Powered by baoer

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付