常系数齐次线性递推式第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))。
我不会魔法的实现
暂时留坑 题目传送门
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605051.html