1.优化dp

观察数据范围并写出转移式，若发现转移次数极多，且从“当前状态”到“下一个状态”的转移公式是完全一模一样的，不跳步（或者可以通过拆分拆成一样的），就可以考虑构造一个初始矩阵（因为要用一个统一的转移矩阵来转移，不能因为跳步而变化），再根据dp转移式构造一个转移矩阵上去转移（乘对应次数次）就行了。初始矩阵相当于dp的初始状态，转移矩阵相当于转移式。部分满足结合律的运算，如加法，乘法，异或出现在转移式中若满足上述条件也可以用矩阵辅助转移。

这里有一种普遍的优化：预处理第$2^n$个矩阵，原因是任何的整数（我们要用到所有的转移次数）都可以用之拼出来，这样我们只需要做一个二进制分解然后直接取值即可。并且$2$的次方的矩阵可以很方便的用快速幂递推地计算出来。
具体怎么计算呢？$T^{2^k} = T^{2^{k-1}} \times T^{2^{k-1}}$。这意味着我们只需要 $O(\log k)$ 次矩阵乘法，就能算出所有需要的 $2$ 的幂次矩阵。高效又方便。

这里每一步运算完后得到的是进行（当前升幂次数）递推后的结果，要与下面的广义矩阵乘法做区分。

2.自定义矩阵计算（广义矩阵乘法）

例题：P6569，P6772
事实上，在大多数情况下，只要一个式子满足结合律，就可使用我们刻画出一种可能的使用矩阵乘法的转移。注意这里是可以使用而不是可以刻画。刻画是一定可以刻画的，转移一次也是可以的，但是转移多次就不一定了，具体见下。
Q1.为什么一定要满足结合律才能使用矩阵乘法转移？
sol：如果不满足就意味着运算分步，括号有顺序，不能一步到位，那进行幂运算就会出现顺序错误的问题，故不行。其实这里和之前优化dp的部分的从“当前状态”到“下一个状态”的转移公式是完全一模一样的差不多。只是这里改成了“是完全一样的操作”。
这里有一种方法。矩阵快速幂优化前想一想，“如果我把两次转移合并成一次，会不会改变原本从左到右的执行顺序？”如果不会（满足结合律）那就上矩阵快速幂。
Q2.证明？

3.小总结

矩阵快速幂的本质，是把 $k$次“一模一样”的转移，通过结合律任意重排括号，从而用 快速幂$O(logk)$次矩阵乘法代替 $O(k)$ 次不俗运算。如果转移本身会变，或者括号不能重排，快速幂就会算错。