该笔记还未完成整理,待日后继续整理……
应用
矩阵加速递推
状态矩阵构造方法
根据题目状态转移方程分析,
选状态为行、选决策为列……
在斐波拉契中:
当前的结果取决于前两个数字(状态),
但这两个数字就是这两个数字,相当于只有一种决策……即$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$……
矩阵快速幂
即为标准快速幂,改为矩阵乘法罢了……
优点
- 时间复杂度:$O(\log n)$
- 因为时间短,便可在较少询问次数的时候,只需要一个矩阵直接去计算,不需要空间开销来存下状态。