欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

常系数齐次线性递推初探

程序员文章站 2022-05-14 09:44:37
~~常系数齐次线性递推式第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。 ......

常系数齐次线性递推式第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)\)

会魔法的实现

暂时留坑 题目传送门