【学习笔记】线性递推数列
1.11.11.1 定义：对于无限数列{a0,a1,a2,...}\{a_0,a_1,a_2,...\}{a0,a1,a2,...}和有限非空数列{r0,r1,r2,...,rm−1}\{r_0,r_1,r_2,...,r_{m-1}\}{r0,r1,r2,...,rm−1}，若对于任意p≥m−1p\ge m-1p≥m−1，有∑k=0m−1ap−krk=0\sum_{k=0}^{m-1}a_{p-k}r_k=0∑k=0m−1ap−krk=0，r0=1r_0=1r0=1，我们称数列rrr为数列aaa的线性递推式。我们称存在线性递推式的无线序列为线性递推数列。r0=1r_0=1r0=1说明ap=−(ap−1r1+...+ap−m+1rm−1)a_p=-(a_{p-1}r_1+...+a_{p-m+1}r_{m-1})ap=−(ap−1r1+...+ap−m+1rm−1)，就是所谓的递推式。
1.21.21.2对于无限数列{a0,a1,a2,...}\{a_0,a_1,a_2,...\}{a0,a1,a2,...}和有限非空序列{r0,r1,r2,...,rm−1}\{r_0,r_1,r_2,...,r_{m-1}\}{r0,r1,r2,...,rm−1}，设数列aaa和数列rrr所对应的生成函数为AAA和RRR，数列rrr为数列aaa的线性递推式等价于存在次数不超过m−2m-2m−2的多项式SSS满足AR+S=0AR+S=0AR+S=0。对于有限数列{a0,a1,a2,...,an−1}\{a_0,a_1,a_2,...,a_{n-1}\}{a0,a1,a2,...,an−1}，则为AR+S=0(modxn)AR+S=0\pmod{x^n}AR+S=0(modxn)。
1.31.31.3 Berlekamp-Massey 算法，先考虑有限的情形。该算法找一个阶数最小的RRR，使得AR=S(modxn)AR=S\pmod{x^n}AR=S(modxn)，且SSS的阶数小于RRR的阶数。具体做法是对于i=2,3,...,ni=2,3,...,ni=2,3,...,n，在modxi\mod{x^i}modxi的意义下递推求出RiR_iRi和SiS_iSi。
假设已经知道 modxi−1\bmod\ {x^{i-1}}mod xi−1 的答案是RiR_iRi，那么求 modxi\bmod\ {x^i}mod xi 的答案RiR_iRi。
1.3.11.3.11.3.1 先检验一下是否有ARi−1=Si−1(modxi)AR_{i-1}=S_{i-1}\pmod{x^i}ARi−1=Si−1(modxi)，如果是，那么Ri=Ri−1R_i=R_{i-1}Ri=Ri−1
1.3.21.3.21.3.2 如果不是，那么有ARi−1−Si−1=dxi−1(modxi)(1)AR_{i-1}-S_{i-1}=dx^{i-1}\pmod{x^i}(1)ARi−1−Si−1=dxi−1(modxi)(1)。考虑上次是再p(p (2)(2)(2) 同时乘xi−pdc−1x^{i-p}dc^{-1}xi−pdc−1，有xi−pdc−1(ARp−1−Sp−1)=dxi−1(modxi)(3)x^{i-p}dc^{-1}(AR_{p-1}-S_{p-1})=dx^{i-1}\pmod{x^i}(3)xi−pdc−1(ARp−1−Sp−1)=dxi−1(modxi)(3) (1)−(3):A(Ri−1−xi−pdc−1Rp−1)=Si−1−xi−pdc−1Sp−1(modxi)(1)-(3):A(R_{i-1}-x^{i-p}dc^{-1}R_{p-1})=S_{i-1}-x^{i-p}dc^{-1}S_{p-1}\pmod{x^i}(1)−(3):A(Ri−1−xi−pdc−1Rp−1)=Si−1−xi−pdc−1Sp−1(modxi) 令Ri=Ri−1−xi−pdc−1Rp−1R_i=R_{i-1}-x^{i-p}dc^{-1}R_{p-1}Ri=Ri−1−xi−pdc−1Rp−1，Si=Si−1−xi−pdc−1Sp−1S_i=S_{i-1}-x^{i-p}dc^{-1}S_{p-1}Si=Si−1−xi−pdc−1Sp−1即可。 初始R0=1,S0=0R_0=1,S_0=0R0=1,S0=0，如果A0A_0A0到Ai−2A_{i-2}Ai−2都是000，而Ai−1A_{i-1}Ai−1不为零，此时修改递推式，让Ri=1+xiR_{i}=1+x^iRi=1+xi，Si=Ai−1xi−1S_i=A_{i-1}x^{i-1}Si=Ai−1xi−1即可。 其最短性不再赘述。由于初值和递推过程中，SiS_iSi次数小于RiR_iRi次数，所以最后得到的结果中，SSS的次数也是小于RRR的次数的。复杂度O(n2)O(n^2)O(n2)。 对于无限长的数列{a0,a1,a2,...}\{a_0,a_1,a_2,...\}{a0,a1,a2,...}，若它的最短线性递推式阶数不超过sss，那么{a0,a1,a2,...,as+s−1}\{a_0,a_1,a_2,...,a_{s+s-1}\}{a0,a1,a2,...,as+s−1}的最短线性递推式即为aaa的最短线性递推式。 1.41.41.4 设已知ai+1=−(ai−n+1bn+ai−n+2bn−1+...+aib1)a_{i+1}=-(a_{i-n+1}b_n+a_{i-n+2}b_{n-1}+...+a_ib_1)ai+1=−(ai−n+1bn+ai−n+2bn−1+...+aib1)，且已知a1∼na_{1\sim n}a1∼n，b1∼nb_{1\sim n}b1∼n，求aka_kak的值。 我们知道AR=SAR=SAR=S，所以A=SRA=\frac{S}{R}A=RS。 问题转化为，求P(x)Q(x)\frac{P(x)}{Q(x)}Q(x)P(x)的第nnn项。因为F(x)=P(x)Q(−x)Q(x)Q(−x)F(x)=\frac{P(x)Q(-x)}{Q(x)Q(-x)}F(x)=Q(x)Q(−x)P(x)Q(−x)，所以Q(x)Q(−x)Q(x)Q(-x)Q(x)Q(−x)只有偶数项不为000，设P(x)Q(−x)=E(x2)+xO(x2)P(x)Q(-x)=E(x^2)+xO(x^2)P(x)Q(−x)=E(x2)+xO(x2)，V(x)=Q(x)Q(−x)V(x)=Q(x)Q(-x)V(x)=Q(x)Q(−x)，所以得到分解P(x)Q(x)=E(x2)V(x2)+xO(x2)V(x2)\frac{P(x)}{Q(x)}=\frac{E(x^2)}{V(x^2)}+x\frac{O(x^2)}{V(x^2)}Q(x)P(x)=V(x2)E(x2)+xV(x2)O(x2)，只需按nnn的奇偶性递归到一侧即可。递归到常数项时答案就是分子分母常数项相除。 复杂度O(nlognlogk)O(n\log n\log k)O(nlognlogk)。 1.51.51.5 求向量/矩阵的最短递推式 考虑将向量/矩阵转化为标量序列的最短线性递推式。具体做法是随机一个向量vvv与每个向量相乘，矩阵的情况也类似。 1.61.61.6 求矩阵的最小多项式 相当于求矩阵{I,M,M2,...}\{I,M,M^2,...\}{I,M,M2,...}的线性递推式，我们知道MMM的最小多项式阶数≤n\le n≤n（特征多项式），所以只需对矩阵{I,M,M2,...,M2n}\{I,M,M^2,...,M^{2n}\}{I,M,M2,...,M2n}应用BMBMBM算法即可。 1.71.71.7 求矩阵的特殊多项式 由于特征多项式是一个nnn阶多项式，所以可以带入n+1n+1n+1个值进去，求nnn个行列式的值，然后插值。复杂度O(n4)O(n^4)O(n4)。