线性递推小结

问题

给定$n,k,f_0\dots f_{k-1},a_1\dots a_{k}$,定义$f_n=\sum_{i=1}^k f_{n-i}a_i$,求$f_n$。

做法

定义$F(A(x))=\sum_{i=0}^nA_if_i$,那么答案就是$F(x^n)$。

由于$f_n=\sum_{i=1}^{k}f_{n-i}a_i$,对于$F(x^n)=F(\sum_{i=1}^{k}a_ix^{n-i})$,所以$F(x^n-\sum_{i=1}^k a_ix^{n-i})=F(x^{n-k}(x^k-\sum_{i=0}^{k-1}a_{k-i}x^i))=0$。

设$G(x)=x^k-\sum_{i=0}^{k-1}a_{k-i}x^i$。

那么$F(A(x)+x^nG(x))=F(A(x))+F(x^nG(x))=F(A(x))$

那么就可以通过多次对$A(x)$加上$x^nG(x)$的倍数来降低A(x)的次数。

也就是求$F(A(x)\bmod G(x))$。显然$A(x)\bmod G(x)$次数$\lt k$,对于$\lt k$的项,$F(x^i)=f_i$已经给出了,所以可以直接算。

通过快速幂+多项式取模,时间复杂度是$O(k\log k\log n)$

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×