矩阵乘法快速幂可以优化以下两种形式的递推式。

1. $f_i= \sum_{j=1}^k f_{i-j} a_j + c_i + c_0$

构造矩阵$\mathrm{F(i)}[1 \times (k+2))$,$\mathrm{R}((k+2)\times(k+2))]$，

$$ \mathbf{F(i)}= \left[ \begin{array}{cccccc} f_i & f_{i-1} & \ldots & f_{i-k+1} & i & 1 \end{array} \right] $$

满足$\mathrm{F(i)}=\mathrm{R} \cdot \mathrm{F(i-1)}$，

$$ \therefore \mathbf{R}= \left[ \begin{array}{ccccccc} a_1 & 1 & 0 & \ldots & 0 & 0 & 0 \\ a_2 & 0 & 1 & \ldots & 0 & 0 & 0 \\ a_3 & 0 & 0 & \vdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ldots & 1 & 0 & 0 \\ a_k & 0 & 0 & 0 & 0 & 0 & 0 \\ c & 0 & 0 & 0 & 0 & 1 & 0 \\ c_0+c & 0 & 0 & 0 & 0 & 1 & 1 \end{array} \right] $$

初始矩阵为$\mathrm{F(n_0)}$，

$\mathrm{F(n)}=\mathrm{R}^{n-n_0} \cdot \mathrm{F(n_0)}$即为所求。

$\because$矩阵乘法满足结合律，

$\therefore \mathrm{R}^{n-n_0}$可以使用快速幂计算。

习题

$poj\ 3744$ 解

$bzoj\ 2326$ 解

$zoj\ 3216$ 解

$bzoj\ 3329$

2. $f_{i,j}=\sum_{k=1}^{n} f_{i-1,k}a_{k,j}$

实际上是一样的。