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

userId_undefined
༺ཌༀཉི༒白·羊༒༃ༀད༻
出道萌新荣耀黄金时空双修者传道者GESP6级CSP-J一等奖

2025-10-06 20:10:05

发布于：上海

51阅读
0回复
0点赞

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

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

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

目录

1. 简介

2. 核心思想

3. 使用条件

4. 代码流程

5. 典例分析

6. 进阶应用

7. 例题

Part 1. 简介

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

Part 2. 核心思想

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

Part 3. 使用条件

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

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

  • 状态转移是线性的：即 dp[i]dp[i] 可以由前面若干个 dp[j]dp[j] 的线性组合得到。

  • 递推系数是常数：不随 ii 的变化而变化。

  • 递推阶数固定：即dp[i]dp[i]只依赖于前面固定kk个状态，如dp[i−1],dp[i−2],…dp[i−k]dp[i-1],dp[i-2],…dp[i-k]。

Part 4. 代码流程

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

dp[n]=a1⋅dp[n−1]+a2⋅dp[n−2]+⋯+ak⋅dp[n−k]dp[n] = a_1 \cdot dp[n-1] + a_2 \cdot dp[n-2] + \dots + a_k \cdot dp[n-k]

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

1. 构造状态向量

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

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

我们的目标是从 Vn−1V_{n-1}推出VnV_n。

2. 构造转移矩阵

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

Vn=M⋅Vn−1V_n = M \cdot V_{n-1}

根据递推关系：

  • 第一行：dp[n]=a1⋅dp[n−1]+a2⋅dp[n−2]+⋯+ak⋅dp[n−k]dp[n] = a_1 \cdot dp[n-1] + a_2 \cdot dp[n-2] + \dots + a_k \cdot dp[n-k]
    ⇒\Rightarrow矩阵第一行为[a1,a2,…,ak][a_1,a_2,\dots,a_k]
  • 第二行：dp[n−1]=1⋅dp[n−1]+0⋅dp[n−2]+0⋅…dp[n-1]=1\cdot dp[n-1]+0\cdot dp[n-2]+0\cdot \dots
    ⇒\Rightarrow矩阵第二行为[1,0,…,0][1,0,\dots,0]
  • 第三行：dp[n−2]=0⋅dp[n−1]+1⋅dp[n−2]+0⋅…dp[n-2]=0\cdot dp[n-1]+1\cdot dp[n-2]+0\cdot \dots
    ⇒\Rightarrow矩阵第三行为[0,1,…,0][0,1,\dots,0]

于是，转移矩阵为：

M=[a1a2a3…ak−1ak100…00010…00⋮⋮⋱⋮⋮⋮00…10000…010]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. 矩阵快速幂

我们有：

Vn=M⋅Vn−1=M2⋅Vn−2=⋯=Mn−k+1⋅Vk−1V_n=M\cdot V_{n-1}=M^2\cdot V_{n-2}=\dots=M^{n-k+1}\cdot V_{k-1}

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

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

Part 5.典例分析

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

Fn=Fn−1+Fn−2,F0=0,F1=1F_n=F_{n-1}+F_{n-2},F_0=0,F_1=1

先构造向量：

Vn=[FnFn−1]V_{n} = \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix}

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

M=[1110]M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}

验证一下：

Vn=M⋅Vn−1  ⟹  [FnFn−1]=[1110][Fn−1Fn−2]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}

初始条件：

V1=[F1F0]=[10]V_1 = \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}

所以：

Vn=Mn−1⋅V1V_n = M^{n-1} \cdot V_1

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

Part 6.进阶应用

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

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

其中

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

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

Vn=[dp[n]dp[n−1]sum[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⋅dp[n−1]+0⋅dp[n−2]+0⋅sum[n−1]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]\\

以及：

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⋅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=[111100112]M = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 2 \end{bmatrix}

验证：

Vn=M⋅Vn−1⇓[dp[n]dp[n−1]sum[n]]=[111100112][dp[n−1]dp[n−2]sum[n−1]]\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}

于是这个问题就解决了。

Part 7. 例题

第一题

第二题

以上两题均为模板题，不做讲解

来道进阶题吧

看似含参，但也不难 还怪押韵，由读者自行完成

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

userId_undefined
去预览
0/2000

全部评论 5

热门讨论