首页 > 代码库 > 用矩阵乘法优化递推
用矩阵乘法优化递推
(有关矩阵乘法的基本规则请自行搜索)
引例:求斐波那契数列的第 n 项 mod 1000000007 的值,n <= 1018。
分析:斐波那契数列的递推式为 f(n) = f(n-1)+f(n-2),直接循环求出 f(n) 的时间复杂度是 O(n),对于题目中的数据范围显然无法承受。很明显我们需要对数级别的算法。
由于 f(n) = 1*f(n-1) + 1*f(n-2) 这样的形式很类似于矩阵的乘法,所以我们可以先把这个问题复杂化一下,将递推求解 f(n) 与 f(n-1) 的过程看作是某两个矩阵相乘的结果,式子如下:
[ f(n-2), f(n-1) ]
*
[ 0, 1 ]
[ 1, 1 ]
=
[ f(n-1), f(n-2)+f(n-1)=f(n) ]
所以我们只要不断地乘以上面式子中的第二个矩阵(也就是第二个矩阵的幂)就能够不断递推得到 f(n)。但是这样于解题没有丝毫益处,反而使得常数变得更大(矩阵乘法的复杂度为立方级别)。所以我们就要利用矩阵乘法的一条重要性质:结合律。即矩阵 (A*B)*C = A*(B*C),证明过程可参见 2008 年国家集训队俞华程的论文。
有了结合律我们就可以用快速幂计算矩阵的幂,问题的复杂度顺利降到了 O(logn)。
?
例:Sam 数
Sam 数是指相邻的两位数字相差不超过 2 的数。求长度为 n 的 Sam 数有多少个。输出对 1000000007 取余后的结果。n <= 10^18。
分析:这个数据范围很吓人,所以必须要 O(logn) 的算法。
首先,递推式很明显:
用 f(i, j) 表示第 j 位为 i 时总的个数(先不考虑各种特殊情况),则
f(i, j) = f(i-2, j-1) + f(i-1, j-1) + f(i, j-1) + f(i+1, j-1) + f(i+2, j-1)
我们考虑这样一个矩阵 A:
[ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
这个 1*10 矩阵表示当第一位为 i 且一共只有 1 位时的方案数。
考虑另一个矩阵 B:
这个矩阵的第 i 行 第 j 列 表示当某一位为 j,相邻一位取 i 时的方案数。
我们将矩阵 A 与 B 相乘一次,可以得到一个 1*10 的矩阵,很明显,这个矩阵的第 i 个元素的值表示当第一位为 i 且一共有 2 位时的方案数,那么矩阵的元素和即 n=2 时的结果。
同理,将 A 不断地与 B 相乘,对于 n,最终得到的矩阵为 A * (B ^ n-1) 的结果,这个矩阵的元素和即最终答案。注意 n=1 的时候特判,这时 0 也算一个方案,所以答案为 10。