矩阵乘法优化 DP

对于一些 DP 转移式，可以将它转换成矩阵乘法，而矩阵乘法满足结合律，所以可以使用快速幂在 $O(\log n)$ 的时间内计算完。

矩阵乘法优化 DP 的条件：

1. 转移式简单，因为转移矩阵不可以改变，所以只能有一次项，如 $f_i=i \times f_{i-1}+f_{i-2}$，但是不能含有 $\max$ 函数和 $\min$ 函数，不能含有 $f_{i-1} \times f_{i-2}$ 之类的式子；
2. 递推次数很多，$O(n)$ 递推无法通过，需要 $O(\log n)$ 算法。

矩阵乘法优化 DP 的步骤：

1. 写好转移式；
2. 构造出转移矩阵；
3. 矩阵快速幂。

如何构造转移矩阵

缺什么补什么，将所有的项加进矩阵。

带常数项 $k$

递推方程：$f_n=f_{n-1}+f_{n−2}+k$

$$f_n=\begin{vmatrix} f_n & f_{n-1} & k \end{vmatrix},\mathrm{base}=\begin{vmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{vmatrix}$$

带未知数项 $n$

递推方程：$f_n=f_{n−1}+f_{n−2}+n$

$$f_n=\begin{vmatrix} f_n & f_{n-1} & n & 1 \end{vmatrix},\mathrm{base}=\begin{vmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 \end{vmatrix}$$

求和

递推方程：$f_n=f_{n-1}+f_{n−2}$

求：$\sum\limits_{i=1}^n{f_i}$

暴力计算 $n$ 次得出 $f_i$ 数组肯定是不行的，但可以尝试将 $S_n$ 放入矩阵跟随着 $f_n$ 一起递推

于是得到一个式子：$S_n=S_{n-1}+f_n$

$$f_n=\begin{vmatrix} f_n & f_{n-1} & S_{n-1} \end{vmatrix},\mathrm{base}=\begin{vmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{vmatrix}$$

例题：矩阵乘法快速幂

例题：线段树上维护矩阵乘法

例题