找到了篇四年前空间中的旧文,也是有点感动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 |
| 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,则乘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.模运算有这样的性质: (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
说点什么
您将是第一位评论人!