#创作计划#矩阵快速幂优化dp

༺ཌༀཉི༒白·羊༒༃ༀད༻

2025-10-06 20:10:05

发布于：上海

25阅读

0回复

0点赞

$\tiny 最近写了四篇创作计划了，我太高产了$

今天我们要讲解的是一种冷门但实用的算法——矩阵快速幂

注意：本篇文章的前置知识是矩阵乘法，碍于时间所限，不做具体讲解

目录

1. 简介

2. 核心思想

3. 使用条件

4. 代码流程

5. 典例分析

6. 进阶应用

7. 例题

Part 1. 简介

矩阵快速幂是一种强大的算法，其主要作用是将 $O(n)$ 的线性 $dp$ 优化为 $O(log n)$ 的快速幂

Part 2. 核心思想

矩阵快速幂的核心思想是：将递推关系表示为矩阵形式，然后利用矩阵乘法的结合律，通过快速幂算法快速计算矩阵的高次幂，从而直接得到递推式第 $n$ 项的值。

Part 3. 使用条件

注意！这个条件肥肠重要！

满足以下条件的 $dp$ 通常可以用矩阵快速幂优化：

状态转移是线性的：即 $dp[i]$ 可以由前面若干个 $dp[j]$ 的线性组合得到。
递推系数是常数：不随 $i$ 的变化而变化。
递推阶数固定：即 $dp[i]$ 只依赖于前面固定 $k$ 个状态，如 $dp[i-1],dp[i-2],…dp[i-k]$ 。

Part 4. 代码流程

假设现在我们要优化这个柿子：

$dp[n] = a_1 \cdot dp[n-1] + a_2 \cdot dp[n-2] + \dots + a_k \cdot dp[n-k]$

需要几步呢？总共分三步：

1. 构造状态向量

我们构造一个包含当前 k 个状态的状态向量：

$V_{n} = \begin{bmatrix} dp[n] \\ dp[n-1] \\ \vdots \\ dp[n-k+1] \end{bmatrix}$

我们的目标是从 $V_{n-1}$ 推出 $V_n$ 。

2. 构造转移矩阵

我们需要找到一个 $k×k$ 的矩阵 $M$ ，使得：

$V_n = M \cdot V_{n-1}$

根据递推关系：

第一行： $dp[n] = a_1 \cdot dp[n-1] + a_2 \cdot dp[n-2] + \dots + a_k \cdot dp[n-k]$
$\Rightarrow$ 矩阵第一行为 $[a_1,a_2,\dots,a_k]$
第二行： $dp[n-1]=1\cdot dp[n-1]+0\cdot dp[n-2]+0\cdot \dots$
$\Rightarrow$ 矩阵第二行为 $[1,0,\dots,0]$
第三行： $dp[n-2]=0\cdot dp[n-1]+1\cdot dp[n-2]+0\cdot \dots$
$\Rightarrow$ 矩阵第三行为 $[0,1,\dots,0]$

于是，转移矩阵为：

$M = \begin{bmatrix} a_1 & a_2 & a_3 & \dots & a_{k-1} & a_k \\ 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 1 & 0 & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & 0 & 0 \\ 0 & 0 & \dots & 0 & 1 & 0 \end{bmatrix}$

3. 矩阵快速幂

我们有：

$V_n=M\cdot V_{n-1}=M^2\cdot V_{n-2}=\dots=M^{n-k+1}\cdot V_{k-1}$

其中 $V_{k-1}$ 是初始向量，即已知条件。

于是我们直接使用快速幂计算 $M_{n-k+1}$ （时间 $O(k^3log n)$ ），然后乘以初始向量 $V_{k-1}$ 得到 $V_n$ ，其第一个元素就是 $dp[n]$ 。

Part 5.典例分析

我们观察斐波那契数列，他的递推式是：

$F_n=F_{n-1}+F_{n-2},F_0=0,F_1=1$

先构造向量：

$V_{n} = \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix}$

得到矩阵（中间我们跳一步）：

$M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$

验证一下：

$V_n = M \cdot V_{n-1} \implies \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix}$

初始条件：

$V_1 = \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$

所以：

$V_n = M^{n-1} \cdot V_1$

$\color{red}于是我们就求出了斐波那契数列$

Part 6.进阶应用

举个更复杂的例子：带前 $k$ 项和的递推，例如：

$dp[n] = dp[n-1] + dp[n-2] + sum[n-1]$

其中

$sum[n] = sum[n-1] + dp[n]$

此时我们构造的向量我们需要包含三个状态：

$V_n = \begin{bmatrix} dp[n] \\ dp[n-1] \\ sum[n] \end{bmatrix}$

构造方程：

$dp[n] = dp[n-1] + dp[n-2] + sum[n-1]\\ dp[n-1] = 1 \cdot dp[n-1] + 0 \cdot dp[n-2] + 0 \cdot sum[n-1]\\$

以及：

$\begin{aligned} sum[n] &= sum[n-1] + dp[n] \\ &= sum[n-1] + (dp[n-1] + dp[n-2] + sum[n-1]) \\ &= dp[n-1] + dp[n-2] + 2 \cdot sum[n-1] \end{aligned}$

整理得到矩阵：

$M = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 2 \end{bmatrix}$

验证：

$\begin{aligned} V_n &= M \cdot V_{n-1} \\ \Downarrow\\ \begin{bmatrix} dp[n] \\ dp[n-1] \\ sum[n] \end{bmatrix} &= \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 2 \end{bmatrix} \begin{bmatrix} dp[n-1] \\ dp[n-2] \\ sum[n-1] \end{bmatrix} \end{aligned}$

于是这个问题就解决了。

这是最近我写的第四篇创作计划，打字不易，点个赞吧！@AC君求精

有帮助，赞一个

去预览

0/2000

全部评论 2

༺ཌༀཉི༒白·羊༒༃ༀད༻
d

2025-10-01 来自上海
0
cjdstttttt
注意到已经有了
https://www.acgo.cn/discuss/study/19325

2025-10-01 来自广东
0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复cjdstttttt
  哇大佬在线
  
  2025-10-01 来自上海
  0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复cjdstttttt
  饿啊精选没了
  
  2025-10-01 来自上海
  0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复cjdstttttt
  发帖前没查索引的后果555
  $\tiny 但我写的也不错吧$
  
  2025-10-01 来自上海
  0