c/c++语言开发共享常系数齐次线性递推初探

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

要做啥？

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

我会矩阵快速幂！

时间复杂度(o(k^3log n))，其中(nle 10^9,kle32000)，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^nbmod 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(klog klog n))。

我不会魔法的实现

暂时留坑 题目传送门