常系数齐次线性递推初探

常系数齐次线性递推式第n项的快速计算初探 xjb学后的xbj胡扯

要做啥？

求\(f[n]=\sum_{i=1}^ka[i]f[n-i]\)，\(a,f[1\to k]\)已经给出。

我会矩阵快速幂！

时间复杂度\(o(k^3\log n)\)，其中\(n\le 10^9,k\le32000\)，emmm。

我会魔法！

设初始状态矩阵为\(s\)，转移矩阵为\(a​\)，不难发现一步转移长得像这个样子（四阶情形）
\[ \begin{bmatrix} f[5]\\ f[4]\\ f[3]\\ f[2] \end{bmatrix} =\begin{bmatrix} a[1]&a[2]&a[3]&a[4]\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ \end{bmatrix} \begin{bmatrix} f[4]\\ f[3]\\ f[2]\\ f[1] \end{bmatrix} \]
构造序列\(c​\)满足\(a^n=\sum_{i=0}^{k-1}c[i]a^i​\)，两边同时右乘\(s​\)，
\[ a^ns=(\sum_{i=0}^{k-1}c[i]a^i)s=\sum_{i=0}^{k-1}c[i]a^is \]
我们的答案为\((a^ns)[k-1,0]\)，注意\(a\)的特征，可以发现，
\[ (a^ns)[k-1,0]=\sum_{i=0}^{k-1} c[i](a^is)[k-1,0]=\sum_{i=0}^{k-1}c[i]f[i+1] \]
所以只要构造出\(c​\)，我们就能\(o(k)​\)地完成答案的计算。所以\(c​\)的构造才是重点啊

令\(g(m)​\)是一个以矩阵为参数的\(k​\)次多项式，并且\(g(a)=o​\)，那么
\[ a^n=p(a)g(a)+q(a)=p(a)g(a)+\sum_{i=0}^{k-1}c[i](a^i)=\sum_{i=0}^{k-1}c[i]a^i \]
所以序列\(c\)就是\(a^n\bmod g(a)\)的系数。所以\(g(m)\)的构造才是重点啊

我会更强力的魔法！

\(k\)阶方阵\(a\)的特征多项式 ​\(p(\lambda)=\det(\lambda i-a)\)。

哈密尔顿–凯莱定理 \(p(a)=o\)。（可以举例子简单验证一下）

于是\(g(m)\)就这样出来了，推式子可得
\[ p(\lambda)=\lambda^k-\sum_{i=1}^ka[i]\lambda^{k-i} \]
然后回代就做完了。取模的那部分是快速幂套多项式取模，所以总的时间复杂度为\(o(k\log k\log n)\)。

我不会魔法的实现

暂时留坑 题目传送门