常系数齐次线性递推

问题是这样的：

对于一个无穷大的递推数列 \(\{h_i\}\) 和长度为 \(k\) 的已知数列 \(\{a_i\}\)，满足\(\forall n, h_n = \sum_{i=1}^k a_i h_{n-i}\) 。 已知 \(h_i (0 \le i < k)\) 求 \(h_n\) 。

直接递推复杂度 \(O(nk)\) ，矩阵快速幂可以做到 \(O(k^3 logn)\) 的复杂度，这里介绍一个更优秀的做法。

结论

便于以后复习，先给出结论。

1. 构造多项式 \(F(x) = x^k - \sum_{i=1}^k a_i x^{k-i}\) 。
2. 求出多项式 \(G(x) = \sum_{i=0}^{k-1} c_i x^i = x^n \bmod F(x)\) 。
3. 有 \(h_n = \sum_{i=0}^{k-1} c_i h_i\) 。

第一步和第三步都是 \(O(k)\) 的，而第二步通过多项式快速幂和多项式取模可以做到 \(O(k\log k\log n)\) 的复杂度。

当然暴力做多项式快速幂和多项式取模也能做到 \(O(k^2 \log n)\) 的复杂度，大多时候这就足够了。

直观理解

不会线性代数也没关系，上面的做法其实有很简单的直观理解。

上述做法的关键在于第二部分，观察 \(H(x) = x^n\) 在对 \(F(x)\) 取模时的过程，
可以发现任意时刻，都有 \(h_n = \sum_i [x^i]H(x) h_i\) 。

也就是说总有以下命题成立，\(H(x)\) 的 \(i\) 次项系数就是 \(h_i\) 对 \(h_n\) 的贡献系数。
这一点不会因减去了若干倍 \(F(x)\) 发生改变。
原因也很简单，每次将 \(H(x)\) 减去 \(x^i F(x)\) ，就相当于把 \(h_{k+i}\) 换成了 \(\sum_{j=1}^k a_j h_{k+i-j}\) 。
本质上是由于 \(F(x) \equiv 0 \pmod{F(x)}\) 等价于 \(x_k \equiv \sum_{i=1}^k a_i x^{k-i} \pmod{F(x)}\) 。

其实自己列竖式算一算 \(x^n \bmod F(x)\) 就能很容易发现这一点。

线代意义

线代基础不行，只能先行告退。🕊🕊🕊🕊🕊