矩阵加速线性递推式（转载）

问题描述:

已知 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           |

| A*a1+B*a0 |

而 A*a1+B*a0 刚好就是 a2 !

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

|    an     |

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

| A*an+B*a(n-1)|

很显然, A*an+B*a(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 = (bj*Mj)*(b(j-1)*M(j-1))*…*(b2*M2)*(b1*M1)*(b0*M0)

若bi=1,则乘Ｍj;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.模运算有这样的性质: (a*b)%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