矩阵快速幂优化

72 阅读 0 评论 48 点赞

我是靠谱客的博主开朗煎蛋，最近开发中收集的这篇文章主要介绍矩阵快速幂优化，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

考虑转移矩阵，若与前面k项有关则大小为k*k,对于第i个答案而言为第一个答案乘上第i个转移矩阵，而第i个转移矩阵可以用第i-1个到第i-k-1个表示，这些矩阵又可以类似地由它们前面的k个矩阵获得，因此任何一个转移矩阵可以用第1到k的矩阵每个矩阵乘以某个系数表示，我们直接对这个表示进行n方的乘法，最后答案就可以由前k个矩阵获得。

同时注意矩阵乘法还可以实现很多序列上某一项只和前面一些项目相关的问题，如快速求出某个关于f(啥啥啥)*m的n次方的式子，n很小但是m很大，且f拥有递推性质，可以构造杨辉三角转移矩阵实现矩阵快速幂优化。