矩阵乘法优化 DP

矩阵快速幂优化常系数齐次线性递推

形如 $$ dp_x=\sum_{i=1}^{d}{dp_{x-i}t_i} $$ 的递推式叫做常系数齐次线性递推。其中 $d\le n$，$t_i$ 只和 $i$ 相关而和 $x$ 无关。

朴素递推的时间复杂度为 $O(nd)$.

利用矩阵快速幂可以在 $O(d^3\log n)$ 的时间复杂度处理常系数齐次线性递推。

我们发现 $dp_x$ 的值只与 $dp_{x-d}$ 到 $dp_{x-1}$ 的值有关。因此我们将这些 $dp$ 值列成一个矩阵，记作 $A_{i-1}$：

\[ \left[ \begin{matrix} dp_{i-d}& dp_{i-d+1}&\cdots& dp_{i-1} \end{matrix} \right] \]

我们发现，对于任意的 $i$，将 $A_{i-1}$ 乘上另一个矩阵 $Op$，就能得到 $dp_i$ 和 $A_i$. 对于普通的常系数齐次线性递推，$Op$ 矩阵如下：

\[ \left[ \begin{matrix} 0&0&0&\cdots&0&0&t_d\\\ 1&0&0&\cdots&0&0&t_{d-1}\\\ 0&1&0&\cdots&0&0&t_{d-2}\\\ 0&0&1&\cdots&0&0&t_{d-3}\\\ &\vdots&&\ddots&&\vdots&\\\ 0&0&0&\cdots&1&0&t_2\\\ 0&0&0&\cdots&0&1&t_1 \end{matrix} \right] \]

该矩阵是一个 $d$ 阶矩阵。我们发现它的前 $d-1$ 列能把 $A_{i-1}$ 中的所有元素向左偏移一个位置，而第 $d$ 列则把 $A_{i-1}$ 中的所有项加起来，放在 $A_i$ 最后一列的位置。由此，我们有：

\[ A_i=A_{i-1}\times Op \]

从而

\[ A_x=A_0\times Op^x \]

由于矩阵乘法满足结合律，因此可以使用矩阵快速幂先求出 $Op^n$，再用 $A_0$ 与之相乘，从而得出 $dp_n$。时间复杂度 $O(d^3\log(n))$. 该算法在 $n$ 很大的时候能减小时间复杂度。