下面来总结一下最近刷过的矩阵加速DP的题目。
普通矩阵快速幂
拆点
如果图中的边有边权而且边权很小，可以考虑拆点。
边化点
如果有一些形如不能走回头路的限制，可以考虑边化点。
bitset优化矩阵乘法
如果矩阵是01矩阵且操作可以用位运算优化，可以考虑bitset优化矩阵乘法
CF576D Flights for Regular Customers
分组
根据矩阵的结合律，可以先将一个矩阵自乘 (p) 次，在将自乘后的矩阵自乘 (n/p) 次。
广义矩阵乘法
考虑这样的式子：
[c[i,j]=igopluslimits_{k=1}^etaleft(a[i,k]otimes b[k,j]
ight)
]
只要满足一下几个条件，该式子就可以作为矩阵乘法进行使用。（主要是满足矩阵乘法的结合律）
- (otimes) 满足交换律、结合律。
- (otimes) 对 (oplus) 有分配率。
P2886 [USACO07NOV]Cow Relays G
二进制拆分
如果有多个询问，且每个询问我们都要对 (n imes n) 的矩阵做快速幂时，可以考虑先将该矩阵的2的整次幂的幂次预处理出来。对于每个询问，我们只需要将询问二进制拆分以后再进行求解。