title: '[动态规划]矩阵加速'
date: 2026-03-31 21:33:43
tags: 动态规划 数论

矩阵加速DP转移

## 前置知识：矩阵快速幂

给定一个 阶的矩阵 以及一个非负整数 ，要计算矩阵 ，当 时， 是 阶单位矩阵 。

即有，其中有 个 。

若 数值小的时候，可以直接暴力计算。但是如果 的情况时，暴力做法必然会超时。

在此之前我们学过快速幂：即利用二进制的思想，将原来的底数不断扩大，做到 的时间复杂度求出一个数的 次方。

i64 binpow(i64 a,i64 b,i64 m) {
  a%=m;
  i64 res=1;
  while(b>0) {
    if(b&1)res=res*a%m;
    a=a*a%m;
    b>>=1;
  }
  return res;
}

利用这个思想，我们可以把矩阵看作一个整体，套上整数快速幂的模板：

//创建Mat结构体，包含矩阵乘法
Mat binpow(Mat A,i64 x,i64 mod){
    Mat I;
    I.init_b();//初始化单位矩阵
    while(x){
        if(x&1) I=I*A;
        A=A*A;
        x>>=1;
    }
    return I;
}

求矩阵的 次方这个问题就迎刃而解了。

矩阵加速

我们知道，动态规划可以看作一个递推的过程。其在遍历的过程中必然会推导出一个状态转移方程，只要整理清楚了这个状态转移方程，就可以对这个状态转移方程进行矩阵加速。举一个非常常见的例子：

斐波那契数列：

前面两个初始值不用太关心，我们主要关心当 时的情况：

我们可以得到：

假设向量 :

因为具有递推关系故存在一个 阶矩阵 于 前面才能进行状态转移，即：

也就是：

然后我们就可以利用矩阵的乘法运算，用待定系数法求出这四个未知数。

于是我们就可以得到：

假设矩阵 经过 自乘之后变成了

由于矩阵乘法就有 ;

矩阵自乘的过程可以运用矩阵快速幂。因此上式所求出的值即是第 项斐波那契数列的值(一般会进行取模操作)。

这样一来我们就可以以 的时间复杂度求出第 项的各个值了。是矩阵的阶数。

例题

https://www.luogu.com.cn/problem/P3216