Open Kewth opened 4 years ago
https://kewth.github.io/2020/04/19/%E5%B8%B8%E7%B3%BB%E6%95%B0%E9%BD%90%E6%AC%A1%E7%BA%BF%E6%80%A7%E9%80%92%E6%8E%A8/#more
问题是这样的：对于一个无穷大的递推数列 ({h_i}) 和长度为 (k) 的已知数列 ({a_i})，满足(\forall n, hn = \sum{i=1}^k ai h{n-i}) 。 已知 (h_i (0 \le i < k)) 求 (h_n) 。直接递推复杂度 (O(nk)) ，矩阵快速幂可以做到 (O(k^3 logn)) 的复杂度，
https://kewth.github.io/2020/04/19/%E5%B8%B8%E7%B3%BB%E6%95%B0%E9%BD%90%E6%AC%A1%E7%BA%BF%E6%80%A7%E9%80%92%E6%8E%A8/#more
问题是这样的：对于一个无穷大的递推数列 ({h_i}) 和长度为 (k) 的已知数列 ({a_i})，满足(\forall n, hn = \sum{i=1}^k ai h{n-i}) 。 已知 (h_i (0 \le i < k)) 求 (h_n) 。直接递推复杂度 (O(nk)) ，矩阵快速幂可以做到 (O(k^3 logn)) 的复杂度，