------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最近写了四篇创作计划了，我太高产了\tiny 最近写了四篇创作计划了，我太高产了最近写了四篇创作计划了，我太高产了
今天我们要讲解的是一种冷门但实用的算法——矩阵快速幂
> 注意：本篇文章的前置知识是矩阵乘法，碍于时间所限，不做具体讲解
> 目录
>
>
> > 1. 简介
> >
> >
> > 2. 核心思想
> >
> >
> > 3. 使用条件
> >
> >
> > 4. 代码流程
> >
> >
> > 5. 典例分析
> >
> >
> > 6. 进阶应用
> >
> >
> > 7. 例题
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PART 1. 简介
矩阵快速幂是一种强大的算法，其主要作用是将O(n)O(n)O(n)的线性dpdpdp优化为O(logn)O(log n)O(logn)的快速幂
PART 2. 核心思想
矩阵快速幂的核心思想是：将递推关系表示为矩阵形式，然后利用矩阵乘法的结合律，通过快速幂算法快速计算矩阵的高次幂，从而直接得到递推式第 nnn 项的值。
PART 3. 使用条件
> 注意！这个条件肥肠重要！
满足以下条件的 dpdpdp 通常可以用矩阵快速幂优化：
* 状态转移是线性的：即 dp[i]dp[i]dp[i] 可以由前面若干个 dp[j]dp[j]dp[j] 的线性组合得到。
* 递推系数是常数：不随 iii 的变化而变化。
* 递推阶数固定：即dp[i]dp[i]dp[i]只依赖于前面固定kkk个状态，如dp[i−1],dp[i−2],…dp[i−k]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] dp[n]=a1 ⋅dp[n−1]+a2 ⋅dp[n−2]+⋯+ak ⋅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 = dp[n]dp[n−1]⋮dp[n−k+1]
我们的目标是从 Vn−1V_{n-1}Vn−1 推出VnV_nVn 。
2. 构造转移矩阵
我们需要找到一个 k×kk×kk×k 的矩阵 MMM，使得：
Vn=M⋅Vn−1V_n = M \cdot V_{n-1} Vn =M⋅Vn−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]dp[n]=a1 ⋅dp[n−1]+a2 ⋅dp[n−2]+⋯+ak ⋅dp[n−k]
⇒\Rightarrow⇒矩阵第一行为[a1,a2,…,ak][a_1,a_2,\dots,a_k][a1 ,a2 ,…,ak ]
* 第二行：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 \dotsdp[n−1]=1⋅dp[n−1]+0⋅dp[n−2]+0⋅…
⇒\Rightarrow⇒矩阵第二行为[1,0,…,0][1,0,\dots,0][1,0,…,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 \dotsdp[n−2]=0⋅dp[n−1]+1⋅dp[n−2]+0⋅…
⇒\Rightarrow⇒矩阵第三行为[0,1,…,0][0,1,\dots,0][0,1,…,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} M= a1
10⋮00 a2 01⋮00 a3 00⋱…… ………⋮10 ak−1 00⋮01 ak 00⋮00
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} Vn =M⋅Vn−1 =M2⋅Vn−2 =⋯=Mn−k+1⋅Vk−1
其中Vk−1V_{k-1}Vk−1 是初始向量，即已知条件。
于是我们直接使用快速幂计算Mn−k+1M_{n-k+1}Mn−k+1 （时间O(k3logn)O(k^3log n)O(k3logn)），然后乘以初始向量 Vk−1V_{k-1}Vk−1 得到 VnV_nVn ，其第一个元素就是 dp[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 Fn =Fn−1 +Fn−2 ,F0 =0,F1 =1
先构造向量：
Vn=[FnFn−1]V_{n} = \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} Vn =[Fn Fn−1 ]
得到矩阵（中间我们跳一步）：
M=[1110]M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} M=[11 10 ]
验证一下：
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} Vn =M⋅Vn−1 ⟹[Fn Fn−1 ]=[11 10 ][Fn−1 Fn−2 ]
初始条件：
V1=[F1F0]=[10]V_1 = \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} V1 =[F1 F0 ]=[10 ]
所以：
Vn=Mn−1⋅V1V_n = M^{n-1} \cdot V_1 Vn =Mn−1⋅V1
于是我们就求出了斐波那契数列\color{red}于是我们就求出了斐波那契数列于是我们就求出了斐波那契数列
PART 6.进阶应用
举个更复杂的例子：带前 kkk 项和的递推，例如：
dp[n]=dp[n−1]+dp[n−2]+sum[n−1]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] 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} Vn = dp[n]dp[n−1]sum[n]
构造方程：
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]\\ 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]
以及：
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} 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]
整理得到矩阵：
M=[111100112]M = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 2 \end{bmatrix} M= 111 101 102
验证：
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} Vn ⇓ dp[n]dp[n−1]sum[n] =M⋅Vn−1 = 111 101 102 dp[n−1]dp[n−2]sum[n−1]
于是这个问题就解决了。
PART 7. 例题
第一题
第二题
以上两题均为模板题，不做讲解
来道进阶题吧
看似含参，但也不难 还怪押韵，由读者自行完成
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
这是最近我写的第四篇创作计划，打字不易，点个赞吧！@AC君求精
