应用

矩阵加速递推

状态矩阵构造方法

根据题目状态转移方程分析，
选状态为行、选决策为列……

在斐波拉契中：

当前的结果取决于前两个数字（状态），
但这两个数字就是这两个数字，相当于只有一种决策……

即$dp[n][1] \leftarrow dp[n-1][1] \& dp[n-2][1]$……

只有一种决策，便可以把列维度给省去……

$mat[1],mat[2]$分别为前一个数和当前数……

在题P4838 P哥破解密码中：

当前的结果取决于上一次状态的三种决策。

即$dp[n][1 \sim 3] \leftarrow dp[n-1][1 \sim 3]$……

$mat[1][],mat[2][]$就是上一次、这一次两状态…
$mat[][1],mat[][2],mat[][3]$就是选$1$个$A$、选$2$个$A$、选$B$的决策……

• 做题记录

递推矩阵计算

构造完状态矩阵后，只需要手动模拟递推，需要加这个元素的令为$1$（要乘$n$便令为$n$），不需要的令为$0$……

若状态矩阵大小为$n*m$，则递推矩阵大小：$m*m$……

矩阵快速幂

即为标准快速幂，改为矩阵乘法罢了……

优点

1. 时间复杂度：$O(\log n)$
2. 因为时间短，便可在较少询问次数的时候，只需要一个矩阵直接去计算，不需要空间开销来存下状态。