问题分析

我们有一个 $k$ 阶线性递推： $ h_n = a_1 h_{n-1} + a_2 h_{n-2} + \dots + a_k h_{n-k}, \quad n \ge k $ 已知 $h_0, h_1, \dots, h_{k-1}$ 以及系数 $a_1, \dots, a_k$，要求 $h_n$，其中 $n$ 可以大到 $10^9$，$k \leq 2000$。

解法1：矩阵快速幂（常规方法）

构造转移矩阵

令向量 $ \mathbf{v}_m = \begin{bmatrix} h_m & h_{m+1} & \dots & h_{m+k-1} \end{bmatrix}^T $ 则递推关系可以写成： $\mathbf{v}_m = M \cdot \mathbf{v}_{m-1}$ 其中 $M$ 是 $k \times k$ 矩阵： $ M = \begin{bmatrix} 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 1 \\ a_k & a_{k-1} & \dots & a_2 & a_1 \end{bmatrix} $ 最后一行是 $a_k, a_{k-1}, \dots, a_1$。

那么： $\mathbf{v}_n = M^{n-k+1} \cdot \mathbf{v}_{k-1}$ 我们要的是 $\mathbf{v}_n$ 的第一个分量 $h_n$。

复杂度

• 矩阵乘法 $O(k^3)$
• 快速幂 $O(\log n)$
• 总复杂度 $O(k^3 \log n)$

对于 $k=2000$，$k^3 = 8\times 10^9$ 太大，不可行。

解法2：多项式乘法与快速幂（$O(k^2 \log n)$）

理论基础

线性递推对应特征多项式： $ P(x) = x^k - a_1 x^{k-1} - a_2 x^{k-2} - \dots - a_k $ 根据 Cayley–Hamilton 定理，$P(M) = 0$，所以 $M^n$ 可以表示为 $I, M, M^2, \dots, M^{k-1}$ 的线性组合。

计算 $x^n \bmod P(x)$，得到： $ x^n \equiv c_0 + c_1 x + \dots + c_{k-1} x^{k-1} \pmod{P(x)} $ 那么： $h_n = \sum_{i=0}^{k-1} c_i h_i$

算法步骤

1. 计算多项式 $r(x) = x^n \bmod P(x)$，其中 $P(x) = x^k - a_1 x^{k-1} - \dots - a_k$
2. 设 $r(x) = c_0 + c_1 x + \dots + c_{k-1} x^{k-1}$
3. 则 $h_n = \sum_{i=0}^{k-1} c_i h_i$

多项式取模快速幂

• 多项式乘法用直接卷积，因为 $k$ 不大
• 每次乘法 $O(k^2)$
• 快速幂 $O(\log n)$ 次乘法
• 总复杂度 $O(k^2 \log n)$

对于 $k=2000$，$k^2 \log n \approx 4\times 10^7$，可行。

样例验证

输入：

n=6, k=4
a = [3, -1, 0, 4]
h = [-2, 3, 1, 5]

递推式： $ h_n = 3 h_{n-1} - h_{n-2} + 0\cdot h_{n-3} + 4 h_{n-4} $

计算：

• $h_4 = 3h_3 - h_2 + 4h_0 = 3\times 5 - 1 + 4\times (-2) = 15 - 1 - 8 = 6$
• $h_5 = 3h_4 - h_3 + 4h_1 = 18 - 5 + 12 = 25$
• $h_6 = 3h_5 - h_4 + 4h_2 = 75 - 6 + 4 = 73$

输出：73

算法实现细节

多项式乘法取模

设 $A(x) = \sum_{i=0}^{k-1} a_i x^i$，$B(x) = \sum_{i=0}^{k-1} b_i x^i$，计算 $C(x) = A(x)B(x) \bmod P(x)$：

1. 先计算完整乘积 $D(x) = A(x)B(x)$，次数最多 $2k-2$
2. 从高次到低次消去：对于 $i \ge k$，$D[i]$ 贡献到 $D[i-k]$ 加上 $D[i] \times a_{k-j}$ 的对应项（具体根据 $P(x)$ 形式）

实际上 $P(x) = x^k - a_1 x^{k-1} - \dots - a_k$，所以： [ x^k \equiv a_1 x^{k-1} + a_2 x^{k-2} + \dots + a_k \pmod{P(x)} ] 用这个关系降次。

复杂度分析

• 多项式乘法取模：$O(k^2)$
• 快速幂：$O(\log n)$ 次乘法
• 总时间复杂度：$O(k^2 \log n)$
• 空间复杂度：$O(k)$

对于 $k \leq 2000, n \leq 10^9$，$k^2 \log n \approx 4\times 10^7$ 运算量，可以在 2 秒内完成。

总结

这道题是线性递推快速计算的经典问题，通过多项式取模快速幂将矩阵快速幂的 $O(k^3 \log n)$ 优化到 $O(k^2 \log n)$，是处理大规模线性递推的必备技巧。