初探常系数齐次线性递推

常系数齐次线性递推

定义

设有数列$a_0, a_1, a_2, \cdots , a_n$满足线性关系,

$$a_n= \sum_{i = 1} ^ k a_{n-i} \times f_i$$

则称这个数列满足$k$阶齐次线性递推关系。

矩阵乘法

设有一个满足齐次线性递推关系的数列$a$， 满足上述定义，现在求$a_n$。

假设现在维护一个列矩阵，行数为$k$，

$$A = \begin{pmatrix}a_n\\a_{n-1}\\ \cdots \\ a_{n-k+2} \\ a_{n-k + 1} \end{pmatrix}$$

设

$$M = \begin{pmatrix} f_1&f_2&f_3&\cdots&f_{k-2}&f_{k-1} \\ 1&0&0&\cdots&0&0 \\ 0&1&0&\cdots&0&0 \\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots \\ 0&0&0&0&1&0 \end{pmatrix}$$

就可得

$$\begin{pmatrix} f_1&f_2&f_3&\cdots&f_{k-2}&f_{k-1} \\ 1&0&0&\cdots&0&0 \\ 0&1&0&\cdots&0&0 \\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots \\ 0&0&0&0&1&0 \end{pmatrix} \times \begin{pmatrix} a_{n-1}\\ a_{n-2}\\ \cdots \\ a_{n-k+1} \\ a_{n-k} \end{pmatrix} = \begin{pmatrix} a_{n}\\ a_{n-1}\\ \cdots \\ a_{n-k+2} \\ a_{n-k+1} \end{pmatrix}$$

接下来用矩阵快速幂就可以做到$O(k^3log_2 n)$了

$$\begin{pmatrix} f_1&f_2&f_3&\cdots&f_{k-2}&f_{k-1} \\ 1&0&0&\cdots&0&0 \\ 0&1&0&\cdots&0&0 \\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots \\ 0&0&0&0&1&0 \end{pmatrix}^n \times \begin{pmatrix} a_{k-1}\\ a_{k-2}\\ \cdots \\ a_{1} \\ a_{0} \end{pmatrix} = \begin{pmatrix} a_{n+k-1}\\ a_{n+k-2}\\ \cdots \\ a_{n+1} \\ a_{n} \end{pmatrix}$$

特征多项式

咕咕咕。