递推关系转矩阵快速幂

69 阅读 0 评论 46 点赞

我是靠谱客的博主苗条书本，最近开发中收集的这篇文章主要介绍递推关系转矩阵快速幂，觉得挺不错的，现在分享给大家，希望可以做个参考。

一些递推关系如f(n) = af(n-1)+bf(n-2)+...+tf(n-k)等，在n很大的时候，O(n)的算法都不能满足要求的时候，往往可以化为矩阵快速幂来做，复杂度可以降为O(logn)，大大减少了运行时间。

如何将一个递推关系式化为矩阵呢？

比如这样一个递推关系: f(n) = 2*f(n-1)+4*f(n-2)

先列出几个等式：

f(n) = 2*f(n-1)+4*f(n-2)

f(n-1) = 2*f(n-2)+4*f(n-3)

然后就有：

就可以将左边矩阵做n-2次幂，再乘初值，得出第一行第一个即为f(n)。

非齐次的也是如此，加一维来填1即可。

题目：HDU 4602 UVA 10870 ZOJ 3690 HDU 2971 HDU 1757

转载于:https://www.cnblogs.com/whatbeg/p/3790419.html

以上就是苗条书本为你收集整理的递推关系转矩阵快速幂的全部内容，希望文章能够帮你解决递推关系转矩阵快速幂所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。