线性递推的求解

参考文献：2019集训队论文，钟子谦《两类递推数列的性质和应用》

这篇文章介绍如何求解，线性递推的应用更多在这里

数列$\{a_0,a_1,\cdots \}$

向量序列$\{v_0,v_1,\cdots\}$

矩阵序列$\{M_0,M_1,\cdots\}$

的线性递推

序列$a_0,a_1,\cdots,a_n$的线性递推的定义应当是

对于一个常数列$r_0,r_1,\cdots,r_m(r_0=1)$

为了便于表示，令

$\lambda(i,r)=\sum_{j=1}^{m}a_{i-j}r_j$

$\Delta(i,r)=\sum_{j=0}^m a_{i-j}$

满足$\forall i\ge m,\Delta(i,r)=0$

这似乎与与平常的认知有一些冲突

$$\$$

求解序列的最短线性递推: Berlekamp-Massey 算法

对于一个$n$个元素的数列$a_{1,\cdots, n}$，求出它的最短线性递推式

为了便于理解约定下文求出的是最小的$m$和对应的$r_1,\cdots r_m$使得$\forall i\in [m+1,n],a_i=\sum_{j=1}^{m}a_{i-j}r_j$

很显然使用高斯消元可以在$O(n^3)$的时间内求解

而$\text{Berlekamp-Massey(BM)}$算法是通过依次对于前$i$项构造，

添加每一项时在$O(n)$的时间内找到一个可行的构造方法，将复杂度降低到了$O(n^2)$

$$\$$ $$\$$

算法过程

为了更好描述，设$r$的阶为$d(r)$

考虑依次加入每个数$a_i$，设当前$d(r)=m$，上一次的递推是$p$,$p$出现不匹配的位置是$f$

特别的，初始状态的递推是$r=\{ \},f=0$

$1.\Delta(i,r)=0$，那么不需要扩展

2.$\Delta(i,r)\ne 0$

$\text{i}.m=0$，此时只有一种情况即插入了第一个$a_i\ne 0$，唯一的递推序列就是$d(r’)=i,r_j=0(j>0)$，此时显然成立

$\text{ii}.m\ne 0$

构造思路是找到一个$r’$使得$\forall j\in[d(r’),i-1],\lambda(j,r’)=0\and \lambda (n,r’)=\Delta(i-1,r)$

那么当前合法的转移就是$r+r’$

设$t=\frac{\Delta(n,r)} {\Delta(f,p)}$

构造$r’=t \cdot x^{i-f-1}(1-p)$

写出来就是

$r’=\{\underbrace{0,\cdots,0},t\cdot (1-p)\}$

$\ \ \ \ \ \ \ \ i-f-1$个$0$

$r’=\{\underbrace{0,\cdots,0},t,-t\cdot p_{1},-t\cdot p_{2}\cdots,-t\cdot p_{d(p)} \}$

$\ \ \ \ \ \ \ \ i-f-1$个$0$

此时，$d(r’)=i-f+d(p)$

当$j\in [d(r’)+1,i-1]$时，$\lambda(j,r’)=\sum_{k=i-f}^{d(r’)}a_{j-k}r’_k$

$=t\cdot( a_{j-(i-f)}-\lambda(j-(i-f),p))$

由于$p$对于$j\in[d(r’)+1-(i-f),i-1-(i-f)]=[d(p)+1,f-1]$，$p$这个递推式成立

即$\lambda(j,r’)=0$

当$j=i$时，

$\lambda(i,r’)=t\cdot (a_{i-(i-f)}+\lambda(i-(i-f),p))=t\cdot \Delta(f,p)$

即$\lambda (i,r’)=\Delta(n,r)$

完成了我们想要的构造，所以每次记录上一次的失配位置，即可找到最小递推式

关于为什么求得的就是最小递推，可以看论文里的证明

求解向量序列的线性递推

对于长度为$n$的向量序列$\{v_0,v_1,\cdots\}$

在模$P$意义下，随机一个向量$u$，构造标量序列$\{v_0u,v_1u,\cdots\}$

构造和求解这个标量序列的线性递推，复杂度均为$O(n^2)$

求得的线性递推也为向量序列的线性递推的概率为$1-\frac{n} {P}$，通常认为不会错

(可以认为复杂度与读入同阶?)

$$\$$

求解矩阵序列的线性递推

对于长度为$n$的矩阵序列$\{M_0,M_1,\cdots\}$

同样在模$P$意义下，随机两个向量$u,v$，构造标量序列$\{uM_0v,uM_1v,\cdots\}$

求解线性递推的复杂度为$O(n^2)$

但是构造标量序列需要计算$n$次向量与矩阵的乘法，复杂度为$O(n^3)$

(可以认为复杂度与读入同阶?)