常系数齐次线性递推
简介
常系数齐次线性递推数列（又称为 C-finite 或 C-recursive 数列）是常见的一类基础的递推数列。
对于数列 \(\left(a_j\right)_{j\geq 0}\) 和其递推式
\[
a_n=\sum_{j=1}^{d}c_ja_{n-j},\qquad (n\geq d)
\]
其中 \(c_j\) 不全为零，我们的目标是在给出初值 \(a_0,\dots ,a_{d-1}\) 和递推式中的 \(c_1,\dots ,c_d\) 后求出 \(a_k\)。如果 \(k\gg d\)，我们想要更快速的算法。
这里 \(\left(a_j\right)_{j\geq 0}\) 被称为 \(d\) 阶的常系数齐次线性递推数列。
Fiduccia 算法
Fiduccia 算法使用多项式取模和快速幂来计算 \(a_k\)，时间为 \(O(\mathsf{M}(d)\log k)\)，其中 \(O(\mathsf{M}(d))\) 表示两个次数为 \(O(d)\) 的多项式相乘的时间。
算法：构造多项式 \(\Gamma(x):=x^d-\sum_{j=0}^{d-1}c_{d-j}x^j\) 和 \(A(x):=\sum_{j=0}^{d-1}a_jx^j\)，那么
\[
a_k=\left\langle x^k\bmod{\Gamma(x)},A(x)\right\rangle
\]
其中定义 \(\left\langle \left(\sum_{j=0}^{n-1}f_jx^j\right),\left(\sum_{j=0}^{n-1}g_jx^j\right) \right\rangle :=\sum_{j=0}^{n-1}f_jg_j\) 为内积。
证明：我们定义 \(\Gamma(x)\) 的友矩阵为
\[
C_\Gamma:=
\begin{bmatrix}
&&&c_d \\
1&&&c_{d-1} \\
&\ddots &&\vdots \\
&&1&c_1
\end{bmatrix}
\]
我们定义多项式 \(b(x):=\sum_{j=0}^{d-1}b_jx^j\) 和
\[
B_b:=\begin{bmatrix}b_0&b_1&\cdots &b_{d-1}\end{bmatrix}^{\intercal}
\]
观察到
\[
\underbrace{\begin{bmatrix}
&&&c_d \\
1&&&c_{d-1} \\
&\ddots &&\vdots \\
&&1&c_1
\end{bmatrix}}_{C_\Gamma}
\underbrace{\begin{bmatrix}
b_0 \\
b_1 \\
\vdots \\
b_{d-1}
\end{bmatrix}}_{B_b}=
\underbrace{\begin{bmatrix}
c_db_{d-1} \\
b_0+c_{d-1}b_{d-1} \\
\vdots \\
b_{d-2}+c_1b_{d-1}
\end{bmatrix}} _ {B_{xb\bmod{\Gamma}}}
\]
且
\[
\begin{aligned}
C_\Gamma&=\begin{bmatrix}B_{x\bmod{\Gamma}}&B_{x^2\bmod{\Gamma}}&\cdots &B_{x^d\bmod{\Gamma}}\end{bmatrix}, \\
\left(C_\Gamma\right)^2&=\begin{bmatrix}B_{x^2\bmod{\Gamma}}&B_{x^3\bmod{\Gamma}}&\cdots &B_{x^{d+1}\bmod{\Gamma}}\end{bmatrix}, \\
\cdots \\
\left(C_\Gamma\right)^k&=\begin{bmatrix}B_{x^k\bmod{\Gamma}}&B_{x^{k+1}\bmod{\Gamma}}&\cdots &B_{x^{k+d}\bmod{\Gamma}}\end{bmatrix}
\end{aligned}
\]
我们将这个递推用矩阵表示有
\[
\begin{bmatrix}
a_{k} \\
a_{k+1} \\
\vdots \\
a_{k+d-1}
\end{bmatrix}=\underbrace{\begin{bmatrix}
&1&& \\
&&\ddots & \\
&&&1 \\
c_d&c_{d-1}&\cdots &c_1
\end{bmatrix}^k} _ {\left(\left(C_\Gamma\right)^{\intercal}\right)^k=\left(\left(C_\Gamma\right)^{k}\right)^{\intercal}}
\begin{bmatrix}
a_0 \\
a_{1} \\
\vdots \\
a_{d-1}
\end{bmatrix}
\]
可知 \(\left(\left(C_\Gamma\right)^{k}\right)^{\intercal}\) 的第一行为 \(B_{x^k\bmod{\Gamma}}\)，根据矩阵乘法的定义得证。
表示为有理函数
对于上述数列 \(\left(a_j\right)_{j\geq 0}\) 一定存在有理函数
\[
\frac{P(x)}{Q(x)}=\sum_{j\geq 0}a_jx^j
\]
且 \(Q(x)=x^d\Gamma\left(x^{-1}\right)\)，$\deg{P}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用