矩阵加速

简介

  • 矩阵加速,用于计算数列的第 n 项(当 n 的数值过大,线性算法超时时)。
  • 这里的数列限指 K 阶常系数线性递推式

原理

矩阵快速幂

大致分三步:

  • 将原式化为矩阵
  • 矩阵乘法分离,建立矩阵递推关系
  • 找到起始项,建立常数矩阵幂关系(可用数学归纳法证明)

K 阶常系数线性递推关系

典例

Fibonacci 第 n 项

  • 考虑以下的递推式

  • 以此先构建关于 递推式的一维矩阵:

构建一个常数矩阵将 的矩阵与 的矩阵建立矩阵递推式

根据 的值,转化为常数矩阵幂计算:

然后,快速幂计算,复杂度

LuoguP1939

考虑

矩阵乘法分离取幂

然后,快速幂即可


  转载请注明: Sshwy's Blog 矩阵加速

 上一篇
图论概览 图论概览
摘要 图 是一个二元组 。 其中 称为顶点集, 称为边集,它们亦可写成 的元素是一个二元组数对,用 表示,其中 。 分类图
2018.10.04
下一篇 
矩阵乘法 矩阵乘法
矩阵定义在数学中,矩阵(Matrix)是一个按照长方阵列排列的复数或实数集合,最早来自于方程组的系数及常数所构成的方阵。例如,矩阵 A: A=\begin{bmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,m
2018.10.03
  目录