常系数线性递推.
- 矩阵快速幂是 $O(k^3\cdot logn)$ 的,不够优秀.观察式子(后续用 $a$ 代替 $h$ ,用 $f$ 代替 $a$ ),
$$
a_n=\sum_{i=1}^k f_i\cdot a_{n-i}
$$
- 注意到任意一项 $a_i$ 都可以被 $\lbrace a_0,a_1,\dots,a_{k-1} \rbrace$ 线性表示,考虑已知 $a_n$ 的线性表示,如何求得 $a_{2n}$ 的线性表示.这里需要利用一个性质,若:
$$
a_n=\sum_{i=0}^{k-1}b_i\cdot a_i
$$
- 则,
$$
a_{n+x}=\sum_{i=0}^{k-1}b_i\cdot a_{i+x}
$$
- 证明应该是显然的,相当于将 $a_x$ 看做这个数列的首项,递推式都是一样的,所以对应系数也是一样的.
- 于是,连续用 $2$ 次该性质可得,
- 这样就用 $\lbrace a_0,a_1,a_2,\dots,a_{2k-2} \rbrace$ 线性表示了 $a_{2n}$ .那么只需要求得 $\lbrace a_k,a_{k+1},a_{k+2},\dots,a_{2k-2} \rbrace$ 的线性表示,然后代进去即可.
- 像快速幂那样做下去,只用做 $logn$ 次.时间复杂度 $O(k^2\cdot logn)$ .
1 |
|