伯利坎普–梅西（Berlekamp–Massey, BM）算法：为给定序列找到长度最小的线性递推关系（最小多项式/线性反馈移位寄存器 LFSR）。常在模素数域下工作，用于预测后续项与 O(k log n) 求第 n 项。时间复杂度 O(N^2)。
Description: Given the first N terms of a sequence over a field (typically mod prime), finds the shortest linear recurrence. Supports fast n-th term via linear-recurrence exponentiation. Time: O(N^2) to build; O(k log n) per n-th term (k = order) Status: tested
-
函数/接口（据实现）
- vector
berlekampMassey(const vector & s) - 输入序列 s（通常在模 p 下），返回最小递推系数 C（长度 k），使得 s[i] = −Σ_{j=1..k} C[j-1] · s[i−j]（按实现约定亦可无负号）。
- ll linearRecurrence(const vector
& C, const vector & init, long long n) - 已知递推系数 C 与前 k 项 init，计算第 n 项（0-index）。用多项式“降维幂”/Kitamasa 方法：O(k log n)。
- 可选：vector
minPoly(const vector & s) 与 nth_term(C, init, n)。
- vector
-
核心思路（BM 迭代）
- 维护当前特征多项式 C(x)、备份多项式 B(x)、当前长度 L、上次更新时刻 m 及当时的误差标量 b。
- 逐项扫 i=0..N−1，计算“差错” d = s[i] + Σ_{j=1..L} C[j]·s[i−j]（在域上）。
- 若 d==0：仅 m++（当前 C 可解释 s[0..i]）。
- 若 d≠0：构造 T(x)=C(x) − (d/b)·x^m·B(x) 修正 C。
- 若 2L ≤ i：更新 L ← i+1−L，B ← 旧 C，b ← d，m ← 1。
- 否则仅设置 C ← T，m++。
- 最终 C 的长度即最小递推阶 k。
-
n 项快速求值（线性递推快速幂）
- 将递推写成向量/多项式形式，使用“多项式平方取模特征多项式”或 Kitamasa：
- 维护向量/系数 f，按二进制指数对转移做快速幂，并每步按 C 做降维（取模）。
- 复杂度 O(k log n)，适合极大 n。
- 亦可转化为 k×k 伴随矩阵的幂并乘初始向量（矩阵幂 O(k^3 log n)；当 k 较大时不如 Kitamasa）。
- 将递推写成向量/多项式形式，使用“多项式平方取模特征多项式”或 Kitamasa：
-
输出语义
- berlekampMassey 返回 C（长度 k）：
- 序列满足 s[n] = Σ_{j=1..k} a_j · s[n−j]（a_j 与 C 的符号/次序视实现）。
- linearRecurrence 返回目标下标 n 处的值。
- berlekampMassey 返回 C（长度 k）：
-
复杂度
- 构建：BM O(N^2)。
- 查询：O(k log n)。
-
使用与注意
- 域要求：标准 BM 需在域上（常用模素数 p）。若模数合成，需分解到素数模并用 081-数论-中国剩余定理 合并，或采用扩展版本。
- 归一化：外部应对输入 s[i] 做模归一化到 [0,p)。
- 边界：序列全 0 时返回空递推（k=0）；短序列时 k ≤ N/2。
- 数值稳定：整域下仅做模运算；需要模逆，见 088-数论-模逆 与 091-数论-模幂。
- 与多项式：结合多项式快速幂/卷积可做“线性递推卷积加速”（见 106-数值算法-线性递推）。