常系数齐次线性递推

问题

给定一个线性递推数列 \{f_i\} 的前 k 项 f_0\dots f_{k-1} ，和其递推式 f_n=\sum_{i=1}^k f_{n-i}a_i 的各项系数 a_i ，求 f_n 。

前置知识

多项式取模。

做法

定义 F(\sum c_ix^i)=\sum c_if_i ，那么答案就是 F(x^n) 。

由于 f_n=\sum_{i=1}^{k}f_{n-i}a_i ，所以 F(x^n)=F(\sum_{i=1}^{k}a_ix^{n-i}) ，所以 F(x^n-\sum_{i=1}^k a_ix^{n-i})=F(x^{n-k}(x^k-\sum_{i=0}^{k-1}a_{k-i}x^i))=0 。

设 G(x)=x^k-\sum_{i=0}^{k-1}a_{k-i}x^i 。

那么 F(A(x)+x^nG(x))=F(A(x))+F(x^nG(x))=F(A(x)) 。

那么就可以通过多次对 A(x) 加上 x^nG(x) 的倍数来降低 A(x) 的次数。

也就是求 F(A(x)\bmod G(x)) 。 A(x)\bmod G(x) 的次数不超过 k-1 ，而 f_{0..k-1} 已经给出了，就可以算了。

问题转化成了快速地求 x^n\bmod G(x) ，只要将 普通快速幂 中的乘法与取模换成 多项式乘法 与 多项式取模 就可以在 O(k\log k\log n) 的时间复杂度内解决这个问题了。

矩阵的解释

该算法由 Fiduccia 在 1985 年提出，对于 t\geq 0 我们定义列向量 v_t 为

v_t=\begin{bmatrix}f_t\\f_{t+1}\\\vdots\\f_{t+k-1}\end{bmatrix}

那么不难发现

\underbrace{\begin{bmatrix}f_{t+1}\\f_{t+2}\\\vdots\\f_{t+k}\end{bmatrix}}_{v_{t+1}}=\underbrace{\begin{bmatrix}&1&&\\&&\ddots&\\&&&1\\a_{k}&a_{k-1}&\cdots&a_{1}\end{bmatrix}}_M\times \underbrace{\begin{bmatrix}f_t\\f_{t+1}\\\vdots\\f_{t+k-1}\end{bmatrix}}_{v_t}

而因为 v_{t+k} 中每一行都满足这个递推关系，我们将 v_{t+k} 描述为一个线性组合如

v_{t+k}=\sum_{i=1}^ka_{i}v_{t+k-i}

有

M^kv_t=\sum_{i=1}^ka_{i}M^{k-i}v_{t}

发现若能将两边的 v_t 消去后得到多项式 \Gamma(x)=x^k-\sum_{i=1}^ka_ix^{k-i} 满足 \Gamma(M)=O 其中 O 为一个 k\times k 的零矩阵。

假设我们要求 M^n 可以构造多项式 f(x)=x^n 那么 f(M)=M^n ，而现在我们可将 f(x) 写成 f(x)=Q(x)\Gamma(x)+R(x) 而其中零矩阵是没有贡献的，那么 f(M)=R(M) 。

但是注意矩阵乘法不满足消去律，此处我们定义矩阵 M 的特征多项式为 \Gamma(x)=\det(xI-M) ，其中 I 为一个 k\times k 的单位矩阵。Cayley-Hamilton 定理指出 \Gamma(M)=O ，我们观察 M 的形式较为特殊，为下 Hessenberg 矩阵，其特征多项式比起一般矩阵更容易计算。

我们从右下角的 2\times 2 矩阵开始计算特征多项式

\Gamma_2(x)=\det\left(\begin{bmatrix}x&-1\\-a_2&x-a_1\end{bmatrix}\right)=x^2-a_1x-a_2

右下角 3\times 3 矩阵按照第一行的余子式展开有

\begin{aligned} \Gamma_3(x)&=\det\left(\begin{bmatrix}x&-1&0\\0&x&-1\\-a_3&-a_2&x-a_1\end{bmatrix}\right)\\ &=x\cdot (-1)^{1+1}\cdot \Gamma_2(x)+(-1)\cdot (-1)^{1+2}\cdot \det\left(\begin{bmatrix}0&-1\\-a_3&x-a_1\end{bmatrix}\right)\\ &=x^3-a_1x^2-a_2x-a_3 \end{aligned}

观察并归纳有

\Gamma(x)=\Gamma_k(x)=x^k-\sum_{i=1}^ka_ix^{k-i}

至此我们可以使用上面的结论。令 g(x)=f(x)\bmod{\Gamma(x)} 有 g(M)=M^n 。而 \deg(g(x))\lt k 显然，令 g(x)=g_0+g_1x+\cdots +g_{k-1}x^{k-1} 那么

M^nv_0=\sum_{i=0}^{k-1}g_iM^iv_0

即

v_n=\sum_{i=0}^{k-1}g_iv_{i}

我们关注 v_0,v_1,\dots ,v_{k-1} 的第一行就是 f_0,f_1,\dots ,f_{k-1} 已知，那么 f_n 可在 O(k) 时间简单得到。求出 g(x) 则可用快速幂和多项式取模与上述解释是一样的。该算法常数较大，使用生成函数可以得到一个常数更小的算法，见 一种新的线性递推计算方法。

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论