矩阵快速幂优化 DP
1. 矩阵快速幂优化 DP 的定义
若目标 DP 满足线性和马尔可夫性，存在 kkk 维状态向量 ViV_iVi 和 k×kk \times kk×k 转移矩阵 MMM，满足
Vi+1=M⋅ViV_{i+1} = M \cdot V_i Vi+1 =M⋅Vi
则
Vn=M n−k⋅VkV_n = M^{\,n-k} \cdot V_k Vn =Mn−k⋅Vk
因为矩阵乘法具有结合律，所以可以利用快速幂将 DP 的时间复杂度优化至 O(k3logn)O(k^3 \log n)O(k3logn)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 一般线性递推的矩阵构建
对于递推
dp[i]=c1dp[i−1]+c2dp[i−2]+⋯+ckdp[i−k]dp[i] = c_1 dp[i-1] + c_2 dp[i-2] + \dots + c_k dp[i-k] dp[i]=c1 dp[i−1]+c2 dp[i−2]+⋯+ck dp[i−k]
状态向量为
Vi=[dp[i], dp[i−1], …, dp[i−k+1]] TV_i = [dp[i],\ dp[i-1],\ \dots,\ dp[i-k+1]]^{\!T} Vi =[dp[i], dp[i−1], …, dp[i−k+1]]T
则转移矩阵为
M=[c1c2…ck−1ck10…0001…00⋮⋮⋱⋮⋮00…10]k×kM = \begin{bmatrix} c_1 & c_2 & \dots & c_{k-1} & c_k \\ 1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & 0 \end{bmatrix}_{k \times k} M= c1 10⋮0 c2 01⋮0 ………⋱… ck−1 00⋮1 ck 00⋮0 k×k
初始向量取 Vk−1=[dp[k−1], dp[k−2], …, dp[0]]TV_{k-1} = [dp[k-1],\ dp[k-2],\ \dots,\ dp[0]]^{T}Vk−1 =[dp[k−1], dp[k−2], …, dp[0]]T。则
dp[n]=(M n−k+1⋅Vk−1)[0]dp[n] = \bigl( M^{\,n-k+1} \cdot V_{k-1} \bigr)[0] dp[n]=(Mn−k+1⋅Vk−1 )[0]
示例代码:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 非齐次多项式驱动项的增广矩阵
设递推包含 ddd 次多项式驱动项 P(i)P(i)P(i)：
dp[i]=∑j=1kcj dp[i−j]+P(i)dp[i] = \sum_{j=1}^k c_j\, dp[i-j] + P(i) dp[i]=j=1∑k cj dp[i−j]+P(i)
将 P(i+1)P(i+1)P(i+1) 按 iii 的升幂展开为 P(i+1)=q0+q1i+q2i2+⋯+qdidP(i+1)=q_0+q_1 i+q_2 i^2+\dots+q_d i^dP(i+1)=q0 +q1 i+q2 i2+⋯+qd id。取多项式基底为升幂排列，构造增广状态向量
Vi=[dp[i], dp[i−1], …, dp[i−k+1], 1, i, i2, …, id]TV_i = [dp[i],\ dp[i-1],\ \dots,\ dp[i-k+1],\ 1,\ i,\ i^2,\ \dots,\ i^d]^{T} Vi =[dp[i], dp[i−1], …, dp[i−k+1], 1, i, i2, …, id]T
总维度为 k+d+1k+d+1k+d+1。递推写作 Vi+1=M⋅ViV_{i+1}=M\cdot V_iVi+1 =M⋅Vi ，转移矩阵具有分块形式
M=[c1c2⋯ckq0q1q2⋯qd10⋯0000⋯001⋯0000⋯0⋮⋮⋱⋮⋮⋮⋮⋮00⋯1000⋯000⋯0(00)00⋯000⋯0(10)(11)0⋯000⋯0(20)(21)(22)⋯0⋮⋮⋮⋮⋮⋮⋱⋮00⋯0(d0)(d1)(d2)⋯(dd)](k+d+1)×(k+d+1)M = \left[ \begin{array}{cccc|cccc} c_1 & c_2 & \cdots & c_k & q_0 & q_1 & q_2 & \cdots & q_d \\ 1 & 0 & \cdots & 0 & 0 & 0 & 0 & \cdots & 0 \\ 0 & 1 &
\cdots & 0 & 0 & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & 1 & 0 & 0 & 0 & \cdots & 0 \\ \hline 0 & 0 & \cdots & 0 & \binom{0}{0} & 0 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 & \binom{1}{0} & \binom{1}{1} & 0 & \cdots & 0 \\ 0 & 0
& \cdots & 0 & \binom{2}{0} & \binom{2}{1} & \binom{2}{2} & \cdots & 0 \\ \vdots & \vdots & & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & \binom{d}{0} & \binom{d}{1} & \binom{d}{2} & \cdots & \binom{d}{d} \end{array} \right]_{(k+d+1)\times(k+d+1)} M= c1 10⋮0000⋮0 c2
01⋮0000⋮0 ⋯⋯⋯⋱⋯⋯⋯⋯⋯ ck 00⋮1000⋮0 q0 00⋮0(00 )(01 )(02 )⋮(0d ) q1 00⋮00(11 )(12 )⋮(1d ) q2 00⋮000(22 )⋮(2d ) ⋯⋯⋯⋯⋯⋯⋯⋱⋯ qd 00⋮0000⋮(dd ) (k+d+1)×(k+d+1)
右下角块为 (d+1)×(d+1)(d+1)\times(d+1)(d+1)×(d+1) 下三角矩阵，其中的第 ppp 行第 ttt 列为 (pt)\binom{p}{t}(tp )，p,t=0,1,…,dp,t=0,1,\dots,dp,t=0,1,…,d，当 t>pt>pt>p 时元素为 000。该块将 [1,i,i2,…,id]T[1,i,i^2,\dots,i^d]^T[1,i,i2,…,id]T 映射为 [1,i+1,(i+1)2,…,(i+1)d]T[1,i+1,(i+1)^2,\dots,(i+1)^d]^T[1,i+1,(i+1)2,…,(i+1)d]T。
递推从 i=1i=1i=1 开始，所有负数下标的 dp[⋅]dp[\cdot]dp[⋅] 均视为 000。初始向量取
V1=[dp[1], dp[0], 0, …, 0, 1, 1, 12, …, 1d]TV_1 = [dp[1],\ dp[0],\ 0,\ \dots,\ 0,\ 1,\ 1,\ 1^2,\ \dots,\ 1^d]^{T} V1 =[dp[1], dp[0], 0, …, 0, 1, 1, 12, …, 1d]T
则
dp[n]=(M n−1⋅V1)[0]dp[n] = \bigl( M^{\,n-1} \cdot V_1 \bigr)[0] dp[n]=(Mn−1⋅V1 )[0]
示例代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 前缀和累加器的嵌入矩阵
对线性递推 dp[i]=∑j=1kcj dp[i−j]dp[i] = \sum_{j=1}^k c_j\, dp[i-j]dp[i]=∑j=1k cj dp[i−j]，需要同时维护前缀和 S[i]=∑t=0idp[t]S[i] = \sum_{t=0}^i dp[t]S[i]=∑t=0i dp[t]。定义增广状态向量
Vi=[dp[i], dp[i−1], …, dp[i−k+1], S[i]]TV_i = [dp[i],\ dp[i-1],\ \dots,\ dp[i-k+1],\ S[i]]^{T} Vi =[dp[i], dp[i−1], …, dp[i−k+1], S[i]]T
维度为 k+1k+1k+1。递推关系对 i≥ki \ge ki≥k 成立，转移矩阵为
M=[c1c2…ck010…0001…00⋮⋮⋱⋮⋮00…10c1c2…ck1](k+1)×(k+1)M = \begin{bmatrix} c_1 & c_2 & \dots & c_k & 0 \\ 1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & 0 \\ \hline c_1 & c_2 & \dots & c_k & 1 \end{bmatrix}_{(k+1)\times(k+1)} M= c1
10⋮0c1 c2 01⋮0c2 ………⋱…… ck 00⋮1ck 000⋮01 (k+1)×(k+1)
最后一行复制系数 c1,…,ckc_1,\dots,c_kc1 ,…,ck 以计算新的 dp[i+1]dp[i+1]dp[i+1]，末列的 111 将旧前缀和 S[i]S[i]S[i] 累加到 S[i+1]S[i+1]S[i+1] 中。
初始向量取
Vk−1=[dp[k−1], dp[k−2], …, dp[0], S[k−1]]TV_{k-1} = [dp[k-1],\ dp[k-2],\ \dots,\ dp[0],\ S[k-1]]^{T} Vk−1 =[dp[k−1], dp[k−2], …, dp[0], S[k−1]]T
其中 S[k−1]=∑t=0k−1dp[t]S[k-1] = \sum_{t=0}^{k-1} dp[t]S[k−1]=∑t=0k−1 dp[t]。则对 n≥k−1n \ge k-1n≥k−1，
S[n]=(M n−k+1⋅Vk−1)[k]S[n] = \bigl( M^{\,n-k+1} \cdot V_{k-1} \bigr)[k] S[n]=(Mn−k+1⋅Vk−1 )[k]
示例代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 高阶依赖与拆点构造
当问题依赖过去的状态，仅记录当前点将无法判断下一步的合法性，需要将状态重新定义为边，以补齐所依赖的历史信息，恢复马尔可夫性。在此类图问题中，前几步所走的边是所需历史信息的载体。
设边集为 EEE，状态向量
Vi=[cnt(e1), cnt(e2), …, cnt(eE)]TV_i = [\mathrm{cnt}(e_1),\ \mathrm{cnt}(e_2),\ \dots,\ \mathrm{cnt}(e_E)]^{T} Vi =[cnt(e1 ), cnt(e2 ), …, cnt(eE )]T
其中 cnt(e)\mathrm{cnt}(e)cnt(e) 表示第 iii 步结束时恰落在边 eee 终点的路径数。转移矩阵 MMM 是 E×EE\times EE×E 的 0-10\text{-}10-1 矩阵，其元素定义为
Me′, e={1,若 end(e)=start(e′) 且满足题设附加约束0,否则M_{e',\,e} = \begin{cases} 1, & \text{若 } \mathrm{end}(e) = \mathrm{start}(e') \text{ 且满足题设附加约束} \\ 0, & \text{否则} \end{cases} Me′,e ={1,0, 若 end(e)=start(e′) 且满足题设附加约束否则
这里 start(e),end(e)\mathrm{start}(e),\mathrm{end}(e)start(e),end(e) 分别表示边 eee 的起点与终点。递推式为 Vi+1=M⋅ViV_{i+1} = M \cdot V_iVi+1 =M⋅Vi 。
初始向量 V1V_1V1 中，以起点出发的边对应的分量为 111，其余分量为 000。则长度为 nnn 的路径中，到达目标顶点 ttt 的路径总数为
ans=∑e: end(e)=t(M n−1⋅V1)e\mathrm{ans} = \sum_{e:\,\mathrm{end}(e)=t} \bigl( M^{\,n-1} \cdot V_1 \bigr)_e ans=e:end(e)=t∑ (Mn−1⋅V1 )e
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 多维状态压缩的向量化矩阵
若 DP 的第二维是有限状态 mask∈{0,1,…,L−1}mask \in \{0,1,\dots,L-1\}mask∈{0,1,…,L−1}，且转移形如
dp[i][new]=∑oldw(old→new) dp[i−1][old]dp[i][\mathrm{new}] = \sum_{\mathrm{old}} w(\mathrm{old} \to \mathrm{new})\; dp[i-1][\mathrm{old}] dp[i][new]=old∑ w(old→new)dp[i−1][old]
则可视为一阶递推，将第二维展平为向量
Vi=[dp[i][0], dp[i][1], …, dp[i][L−1]]TV_i = [dp[i][0],\ dp[i][1],\ \dots,\ dp[i][L-1]]^{T} Vi =[dp[i][0], dp[i][1], …, dp[i][L−1]]T
转移矩阵 MMM 是 L×LL\times LL×L 的邻接矩阵，其元素为
M[new][old]=w(old→new)M[\mathrm{new}][\mathrm{old}] = w(\mathrm{old} \to \mathrm{new}) M[new][old]=w(old→new)
权值 www 直接编码状态机的一切转移，常取 000 或 111。递推写作 Vi=M⋅Vi−1V_i = M \cdot V_{i-1}Vi =M⋅Vi−1 。
初始向量 V0V_0V0 由初始分布 dp[0][mask]dp[0][mask]dp[0][mask] 直接给出。则
dp[n][mask]=(M n⋅V0)[mask]dp[n][mask] = \bigl( M^{\,n} \cdot V_0 \bigr)[mask] dp[n][mask]=(Mn⋅V0 )[mask]
此式对应于一般形式中取 k=1k=1k=1 的特例。
