Berlekamp-Massey 算法

Berlekamp-Massey 算法是一种用于求数列的最短递推式的算法。给定一个长为 的数列，如果它的最短递推式的阶数为 ，则 Berlekamp-Massey 算法能够在 时间内求出数列的每个前缀的最短递推式。最坏情况下 ，因此算法的最坏复杂度为 。

定义

定义一个数列 的递推式为满足下式的序列 ：

其中 。 称为该递推式的 阶数。

数列 的最短递推式即为阶数最小的递推式。

做法

与上面定义的稍有不同，这里定义一个新的递推系数 ，满足：

容易看出 ，并且阶数 与之前的定义是相同的。

我们可以增量地求递推式，按顺序考虑 的每一位，并在递推结果出现错误时对递推系数 进行调整。方便起见，以下将前 位的最短递推式记为 。

显然初始时有 。假设递推系数 对数列 的前 项均成立，这时对第 项就有两种情况：

1. 递推系数对 也成立，这时不需要进行任何调整，直接令 即可。
2. 递推系数对 不成立，这时需要对 进行调整，得到新的 。

设 ，即 与 的递推结果的差值。

如果这是第一次对递推系数进行修改，则说明 是序列中的第一个非零项。这时直接令 为 个 即可，显然这是一个合法的最短递推式。

否则设上一次对递推系数进行修改时，已考虑的 的项数为 。如果存在一个序列 ，满足：

并且 ，那么不难发现将 与 按位分别相加之后即可得到一个合法的递推系数 。

考虑如何构造 。一种可行的构造方案是令

其中前面一共有 个 ，且最后的 表示将 每项乘以 后接在序列后面。

不难验证此时 ，因此这样构造出的是一个合法的 。将 赋值为 与 逐项相加后的结果即可。

如果要求的是符合最开始定义的递推式 ，则将 全部取相反数后在最开始插入 即可。

从上述算法流程中可以看出，如果数列的最短递推式的阶数为 ，则算法的复杂度为 。最坏情况下 ，因此算法的最坏复杂度为 。

在实现算法时，由于每次调整递推系数时都只需要用到上次调整时的递推系数 ，因此如果只需要求整个数列的最短递推式，可以只存储当前递推系数和上次调整时的递推系数，空间复杂度为 。

朴素的 Berlekamp-Massey 算法求解的是有限项数列的最短递推式。如果待求递推式的序列有无限项，但已知最短递推式的阶数上界，则只需取出序列的前 项即可求出整个序列的最短递推式。（证明略）

应用

由于 Berlekamp-Massey 算法的数值稳定性比较差，在处理实数问题时一般很少使用。为了叙述方便，以下均假定在某个质数 的剩余系下进行运算。

求向量列或矩阵列的最短递推式

如果要求向量列 的最短递推式，设向量的维数为 ，我们可以随机一个 维行向量 ，并计算标量序列 的最短递推式。由 Schwartz-Zippel 引理，二者的最短递推式有至少 的概率相同。

求矩阵列 的最短递推式也是类似的，设矩阵的大小为 ，则只需随机一个 的行向量 和一个 的列向量 ，并计算标量序列 的最短递推式即可。由 Schwartz-Zippel 引理可以类似地得到二者相同的概率至少为 。

优化矩阵快速幂

设 是一个 维列向量，并且转移满足 ，则可以发现 是一个不超过 阶的线性递推向量列。（证明略）

我们可以直接暴力求出 ，然后用前面提到的做法求出 的最短递推式，再调用

常系数齐次线性递推 即可。

如果要求的向量是 ，则算法的复杂度是 。如果 是一个只有 个非零项的稀疏矩阵，则复杂度可以降为 。但由于算法至少需要 的时间预处理，因此在压力不大的情况下也可以使用 的线性递推算法，复杂度同样是可以接受的。

求矩阵的最小多项式

方阵 的最小多项式是次数最小的并且满足 的多项式 。

实际上最小多项式就是 的最小递推式，所以直接调用 Berlekamp-Massey 算法就可以了。如果 是一个 阶方阵，则显然最小多项式的次数不超过 。

瓶颈在于求出 ，因为如果直接每次做矩阵乘法的话复杂度会达到 。但考虑到求矩阵列的最短递推式时实际上求的是 的最短递推式，因此我们只要求出 就行了。

假设 有 个非零项，则复杂度为 。

求稀疏矩阵行列式

如果能求出方阵 的特征多项式，则常数项乘上 就是行列式。但是最小多项式不一定就是特征多项式。

实际上如果把 乘上一个随机对角阵 ，则 的最小多项式有至少 的概率就是特征多项式。最后再除掉 就行了。

设 为 阶方阵，且有 个非零项，则复杂度为 。

求稀疏矩阵的秩

设 是一个 的矩阵，首先随机一个 的对角阵 和一个 的对角阵 , 然后计算 的最小多项式即可。

实际上不用调用矩阵乘法，因为求最小多项式时要用 乘一个向量，所以我们依次把这几个矩阵乘到向量里就行了。答案就是最小多项式除掉所有 因子后剩下的次数。

设 有 个非零项，且 ，则复杂度为 。

解稀疏方程组

问题：已知 , 其中 是一个 的 满秩 稀疏矩阵， 和 是 的列向量。 已知，需要在低于 的复杂度内解出 。

做法：显然 。如果我们能求出 () 的最小递推式 (), 那么就有结论

（证明略）

因为 是稀疏矩阵，直接按定义递推出 即可。

同样地，设 中有 个非零项，则复杂度为 。

例题

1. LibreOJ #163. 高斯消元 2
2. ICPC2021 台北 Gym103443E. Composition with Large Red Plane, Yellow, Black, Gray, and Blue