常系数齐次线性递推初探
常系数齐次线性递推式第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)\)。
我不会魔法的实现
暂时留坑 题目传送门
推荐阅读