核心概述
线性递推快速求项：在给定阶数 k 的线性递推与初始值下，使用 Kitamasa 或“多项式模特征多项式”的快速幂，在 O(k^2 log n) 或 O(k log k log n) 时间内返回第 n 项。
原文引述
Description: Compute n-th term of linear recurrence of order k using Kitamasa or polynomial exponentiation modulo characteristic polynomial. Works over any field (e.g. mod prime). O(k^2 log n) simple, O(k log k log n) with NTT. Time: O(k^2 log n) naive; O(k log k log n) with FFT/NTT Status: tested ——摘自本节点现有英文注释
展开阐述
-
定义与问题形式
- 递推：a_n = Σ_{i=1..k} c_i·a_{n−i}（常见为常系数线性递推）。
- 初始：a_0, a_1, …, a_{k−1}。
- 目标：对大 n（可至 10^{18} 量级）求 a_n。
-
Kitamasa 算法（O(k^2 log n)）
- 设特征多项式 C(x) = x^k − Σ_{i=1..k} c_i·x^{k−i}。
- 返回系数 d[0..k−1] 使 a_n = Σ d[i]·a_i（n<k 为基例）。
- 分治 n：先解 d1 表示 a_{⌊n/2⌋}，再做 d2 = d1 与自身的卷积；若 n 为奇，加一次由递推系数定义的“进一”算子。
- 每次卷积后按 C(x) 做多项式取模降到次数 < k。
- 输出 a_n = Σ d[i]·a_i。
-
多项式快速幂法（等价表述）
- 计算 X^n mod C(x) 得 Q(x)=Σ_{i=0..k−1} q_i x^i。
- a_n = Σ q_i·a_i。
- 乘法复杂度：朴素 O(k^2)，若域支持快速卷积可用 FFT/NTT 达到 O(k log k)；整体乘法次数 O(log n)。
-
接口/数据与输入输出（据仓库约定）
- solveLinearRecurrence(c[1..k], a[0..k−1], n) → a_n（必要时在模 p 下返回 a_n mod p）。
- 多项式法需要“多项式乘/模”的实现；Kitamasa 需要“系数卷积 + 按 C(x) 降阶”。
-
数值稳定性/精度与实现要点
- 在模域下进行时：统一使用 094-数论-模运算 的规约；乘逆元与快速幂分别见 088-数论-模逆、091-数论-模幂。
- 系数约定需与实现一致（是否使用 x^k = Σ c_i x^{k−i} 的符号/次序约定）。
- 主要瓶颈常在 k；当 k 较大时优先使用 NTT 加速卷积（依赖 099-数值算法-模域FFT、098-数值算法-快速傅里叶变换）。
-
复杂度与边界条件、常见变体/扩展
- Kitamasa：O(k^2 log n)。
- 多项式法：朴素 O(k^2 log n)；NTT 版 O(k log k log n)。
- 变体：先用 096-数值算法-伯利坎普梅西 从前若干项求最短递推，再用本模板求第 n 项。
-
正确性要点与不变式
- 任何时刻表示向量/多项式均等价于“用初始项线性组合得到 a_t”的不变式；按 C(x) 模降保证次数不超过 k−1。