多项式和递推

发表于 分类于 ， 阅读次数：

本文共约 9300 字。

Key Words：线性递推，Berlekamp-Massey 算法，整式递推，微分有限（D-finite），微分方程，快速阶乘算法，二维递推（多项式递推），斯特林数，欧拉数，附加因子法，基变换换元

线性递推

  • 线性递推

    对于数列 ，若存在 使得 则称 为线性递推数列。

求线性递推的单项

数列 有递推公式 。

给出 ，求 的值。

多项式取模

维护一个无穷数列 ，令 初始时令 ，则 。

根据递推式，我们知道 可以替换成 于是可以对 进行如下操作：选定 ，将 减 ，将 增加 ，将 增加 ……将 增加 。这样操作后的 不变。

从高位到低位执行替换操作，这和大除法非常相似。构造特征多项式 ，不上述规则相当于将 对 取模。

用快速幂计算 ，把 约化为只有 有值，则 。这相当于对 求出 对 的贡献系数。

复杂度 。

获得线性递推数列的生成函数

注意到递推式很像卷积。令 ，则 ，故 的 及以上项都是 。

记 ，此处 的次数小于 ，我们已经知道 即 ，故可以用 计算 。

最终

根据多项式求逆的递推算法，我们知道任意分式 的系数也一定是线性递推。线性递推本质上就是分式的系数。

Bostan–Mori 算法

根据前文，我们可以 构造出 使得 ，目标是 。

分子分母同乘 得 记 ，注意到 ，这说明 无奇数次项，于是记 。

记 ，将 奇偶项拆分为 使得 ，则 其中 只有偶数项， 只有奇数项，递归到一侧即可。即 其中 的次数仍不超过 。

递归会进行 轮，每轮有两次多项式乘法计算 ，复杂度 。

Berlekamp-Massey 算法

  • 给出 项数列 ，求 的最短线性递推式。

记 ，根据上一节的讨论，要求出一种递推式，相当于求出 满足 且 。

BM 算法的思路是增量法，假设我们已经求出 ，考虑如何构造 使得 。

若幸运地，，保持 不变即可。若两者不等，只可能是 系数不等，即 ，称为一次“失配”。

假设递推式上一次变长是 ，这也是“失配” ，考虑利用配凑将两个余项对消。要使得两个同余式次数相等，对 乘 ，再将两者相减得 那么，只需要令 由 ，可知 。

（事实上，利用任意一次“失配”即可得到正确的构造，使用“上一次变长”的位置，是为了保证递推式最短）

具体实现时，计算是否失配，只需 算出新的 项，构造新的 也只需要 的加法，复杂度 。

边界：找出 的最低次项 ，令 即可，然后令 充当第一次失配的情形。

  • 定理 BM 算法求出的递推式为最短递推式。

证明略。

实际应用中，往往已知无穷数列 是有限阶的线性递推，此时取 的足够长的前缀求解 BM 算法，即可得到 的递推公式。具体地：

  • 定理 若无限数列 是 阶线性递推，取 的前 项求出最短递推式，即为 的递推式。

证明：反证法，假设存在两种不同的不超过 阶的递推式，即 满足 且 。

两侧同乘 得 ，注意到两侧次数都小于 ，故 即两种递推式本质相同，矛盾。

故至多只存在一种符合要求的不超过 阶的递推式，即为 的递推式。

线性递推的性质

  • 线性递推的封闭性
    • 线性递推数列的线性组合是线性递推数列。
    • 线性递推数列的加法卷积是线性递推数列。
    • 线性递推数列的点积是线性递推数列。

证明：性质一、二：线性递推等价于分式 的系数，根据分式加法和乘法的封闭性，可证。

性质三：根据特征根法，线性递推数列可以表示为若干等比数列（公比是特征根）的线性组合（反之也成立）。对于线性递推数列 ，设 则 也是若干等比数列的线性组合。

  • 矩阵幂的线性递推

    为 阶方阵，则矩阵列 存在不超过 阶的线性递推式。

证明：记 的特征多项式为 根据 Cayley-Hamilton 定理 这是矩阵列 的一个 阶递推式。

整式递推与 D-finite

基本概念

  • 整式递推

    对于无穷数列 ，若存在不超过 次的多项式 使得 则称 为整式递推数列。

不难发现，线性递推是整式递推的一种特例。

最简单的整式递推是阶乘 ，满足递推公式 。

不加证明地给出如下性质。

  • 微分有限（D-finite）

    若存在不超过 次的多项式 ，使得如下微分方程（ODE） 恒成立，则称 微分有限。

  • 定理 数列 为整式递推，当且仅当 的生成函数 微分有限。

证明：若 微分有限，对于充分大的 ，对其微分方程提取 系数得 注意到 是 的多项式，这是 的整式递推。

反之，在下降幂基 上取合适的系数 ，则 可表示任意多项式，即所有整式递推都有对应的微分方程。

例如： 满足 ，提取 系数得 这是 的整式递推。

整式递推的性质

首先我们要判断一个数列是否拥有整式递推，这相当于研究生成函数的 D-finite 性质。

  • 代数形式幂级数

    若形式幂级数 是某个多项式方程

    的解，其中 是整式，则称 是“代数的”。

易知用（有限次）加减乘除和 次幂构造出来的多项式都是代数的。如 是代数的，而 不是代数的。

不加证明的给出如下性质：

  • D-finite 的性质
    • 如果 是代数的，那么它微分有限。
    • 如果 微分有限，则 微分有限。
    • 如果 微分有限， 是代数的，则 微分有限。（注意，不保证 微分有限）
  • 整式递推的封闭性
    • 整式递推数列的线性组合是整式递推数列。
    • 整式递推数列的加法卷积是整式递推数列。
    • 整式递推数列的点积是整式递推数列。

根据这些性质，我们可以推定一大类函数的 D-finite 性质，如：易知 微分有限，立即可以得到 微分有限。

待定系数法

对于常见的生成函数，预知 D-finite 性质是较为容易的，但它们所满足的微分方程可能非常复杂，难以手工计算。这时，可以用待定系数法（高斯消元）得到整式递推式。

设定最大阶数 ，最大次数 ，求出数列 的足够长前缀 ，解线性方程组 其中 为待定系数。共 个未知量， 条方程，进行高斯消元。

注意，得到的递推式可能不唯一。在解线性方程组的过程中，若遇到自由变量，选择一个赋值为 ，其余赋值为 即可（避免得到全 ）。

例如，计算可知 的系数 满足整式递推

常用微分方程（ODE）

超几何数列

  • 若数列 满足相邻两项之比 是 的有理分式，则称 是超几何数列。

以超几何数列为系数的生成函数称作超几何级数。根据定义易知：超几何数列属于整式递推数列的一种，超几何级数微分有限，而且微分方程容易推导。

通过微分方程，可以解出部分超几何函数的封闭形式。如 满足微分方程 解得 （对比 易知 ），这和我们熟知的结论相同。

以下是一些常见超几何级数的微分方程。 超几何级数微分方程 超几何级数的“截断”也具有简单的微分方程，如 超几何级数（截断）微分方程 这些微分方程是不齐次的，会留有（代数的）尾项 等。

微分方程的复合

若 具有简单的微分方程， 是任意形式幂级数，可以用链式法则求出 的微分方程。

如“部分 exp”：设 ，给出 ，欲求 。

已知 满足微分方程 代入 得 根据 ，记 ，整理得 的微分方程 已知 的系数，牛顿迭代可以 求出 的前 项。

此外，若 的形式很简单，最终 的方程也可以相对简单，我们可以算出其具体形式。

当微分方程不齐次（带有尾项时），计算可能较为繁琐。此时可以进行如下简化：

若 满足非齐次微分方程 ，尾项是代数的， 是代数的，则 满足非齐次微分方程 ，尾项是代数的。可以手工推导 ，但计算可能较为复杂。将 的尾项抹除得到齐次微分方程 ，记对应的解为 ，计算 的齐次微分方程 ，则 和 之间之差一个（代数的）尾项，可以待定系数处理。

求整式递推的单项

在前文中，我们通过 计算整式递推去除了传统做法复杂度中的 因子。下面我们来研究以低于 的复杂度求出整式递推数列 的远处项 。

快速阶乘算法

先来看最简单的整式递推数列 。

  • 多点求值法

构造多项式 ，可以 倍增求出 。

本质上是 的连乘积，而 的点值 是区间 的连乘积，考虑用 的若干点值（区间连乘积）拼起来得到 。

具体地，取 ，多点求值计算 ，，将他们相乘，就能得到 的连乘积。，余下的 不超过 个数，暴力计算。

复杂度 ，取 得最优复杂度为 。

  • 维护点值法

上一个算法复杂度瓶颈在于 的多点求值，考虑不维护多项式的系数表示，直接维护点值。

定义 ，我们需要 个点值就能确定 。

先确定块长 ，不妨假设我们手中的点值是 ，，考虑如下两个操作。

  • 操作一：令 加一，求出 ，。

  • 操作二：令 乘二，求出 ，。

若能实现这两个操作，可以 轮倍增得到 ，。

下面介绍具体解决方案。

  • 操作一：，前 项递推，多出的末项 暴力计算。复杂度 。

  • 操作二：首先使用“Luogu5667 拉格朗日插值2”平移点值，计算出 ，然后有 。复杂度 。

倍增复杂度递推式 ，得 。令 ，总复杂度 。

一般情形

现在我们尝试处理一般的整式递推，可以将计算阶乘的两种算法简单地类比过来。

数列 是整式递推数列，存在不超过 次的多项式 使得 给出 ，求 。

  • 多点求值法

模仿线性递推的矩阵优化，将 记为向量 （下标 ），根据递推式，容易写出转移矩阵 使得 。

具体地，根据

构造 ，最后将整个矩阵除以 即可。

求出乘积 ，再乘上初始给出的 即可得到答案 。

分母上的 不便处理，将其摘除，最后再对答案乘以 即可。（这个乘积显然是一阶整式递推，处理方法类似）

于是， 中的每个元素可以看做关于 的多项式，记这样的多项式矩阵为 。

仍然考虑分块，设块长为 ，求出多项式矩阵 ，然后多点求值即可完成任务。（还需要乘以 个末尾零散的矩阵）

用多项式平移（复合 ）可以 倍增求出 。

多点求值的复杂度是 ，计算数值矩阵乘法的复杂度为

取 得总复杂度 。

  • 维护点值法

方法类似，记 ，确定块长 ，维护 个点值矩阵 。

  • 操作一（令 加一）：，前 项递推，多出的 个末项 暴力计算。复杂度 。

  • 操作二（令 乘二）：首先使用“Luogu5667 拉格朗日插值2”平移点值，计算出 ，然后有 。复杂度 。

可以倍增求出 的点值（矩阵），需将 设为 。（末尾零散的矩阵的个数是 ，需要暴力乘上）

总复杂度 ，取 得复杂度 。

实践中， 一般是常数，两个算法的复杂度分别为 和 。

二维递推

常系数二维递推

组合数

组合数可以视作（最简单的）二维递推产生的数。我们抛弃其组合意义，只从递推式出发，看看能得到什么结果。

记 ，根据递推式

边界 ，易得 ，这就是经典二项式定理。

写出二元生成函数 得

简单递推一例

系数与行有关的二维递推

  • 例题 6.4.7.

    多项式数列 满足如下递推式

    边界为 ，求 。

Solution：

（法一）转移可以写作 的多项式矩阵，分治 FFT 即可算得 。复杂度 。

（法二）为了消除递推式中不对齐的 ，记 ，得 建立 的二元函数 ，则 根据一阶微分方程的解，得到封闭形式 取 对比易知 。 接下来的任务是“幂的横截”，复杂度 。（所需的复合逆显然存在）

对于以上两例，我们将二维递推的一行 封装成生成函数 ，然后处理一维生成函数序列 的递推关系。

其中，常系数二维递推对应 的线性递推，系数与行（）有关则类似整式递推。

系数与列有关的二维递推

若递推式系数和列有关，多项式数列不能被写成简单的整式递推，需要引入微分。

两类斯特林数是很好的例子。由于它们背后的组合意义较为简洁，解析组合方法收效良好。但是，并非所有递推式都有好的（或显然的）组合背景，下面是一个略有变易的例子。

  • 例题 6.4.8. 带符号第二类斯特林数

    二维数阵 满足如下递推关系 给出 ，对 ，求出 。

Solution：有三种方法处理这个递推式。方法一通过翻转避开了难点，但复杂度较劣；方法二通过解析组合轻松解决，但需要一定的观察能力；方法三是纯代数手段，但需要求解偏微分方程。

  • 方法一：转化为多项式整式递推

注意到 的系数只跟列有关，将其行列翻转变成只跟行有关，则转化为多项式整式递推。

记行的生成函数 ， 即为所求。有递推式 转移可以写作 的分式矩阵，分治 FFT 即可算得 。复杂度 。

  • 方法二：考虑递推式的组合意义，解析组合

的递推式和第二类斯特林数的递推式十分相似，故有组合意义： 为 个有标号的球放入 个无标号盒子里，无空盒的方案数，且每多一个球或盒子，贡献乘以 。

以 统计盒子个数（OGF）， 统计球个数（EGF），单个盒子的生成函数为 。根据有标号 SET 变换， 的二元生成函数为 目标是求出 ，多项式 exp 即可。复杂度 。

  • 方法三：直接解偏微分方程

记 ，仍然记二元生成函数 ，尝试得到 的封闭形式并提取系数。

由 的递推式得 此处需要解一阶偏微分方程，可得通解为 ，其中 是任意函数。对比 ，可知 ，故 ，接下来同法二。

一类常见的微分递推

更一般地，考虑如下模型：

多项式序列 满足 ，递推式为

首先运用附加因子法简化递推式。

将递推式改写为一阶线性常微分方程的标准形式 根据通解，有 其中 。

这启示我们构造 （ 即为附加因子），然后 注意， 的封闭形式可能很难计算，但在实践中直接取前 项截断进行运算即可，封闭形式不是必要的。

接下来，解决关于这个递推式的两类任务。

  • 任务一：求

只需求 ，然后乘以 即可。

如果 是单项式，追踪每个系数的贡献，容易 得到 。

如果 不是单项式，附加因子法难以处理，考虑使用复合的手段，即基变换换元。

考虑递推式 ，它是容易解决的。尝试对其右复合 得 记 ，则 满足递推式 这可以用来解决 的递推，只需 。解得 ，其中 为任意常数。为了 有复合逆，不妨取 。

或者利用递推式 ，右复合 也可行，此时需要 。（可以尝试其他递推式，如 ，一般没有什么简化）

的递推容易计算，故我们只需计算 之间的变换，即右复合（与复合逆）。在 和 之间，选取那个使 更简便的形式。

例如如下递推式 构造 ，计算得 ，其复合容易计算。

  • 任务二：对 求出

（同【例题 6.4.8】方法一）可以将系数行列翻转，从而将列相关（微分）转化为行相关，进而用分治 FFT 解决。（如果 为短多项式）复杂度 。

若需要更优的复杂度，建立二元生成函数 ，则 解偏微分方程，得 ，其中 是任意函数。

对比 ，记 ，其复合逆是 ，则 ，于是可得 的封闭形式。

的二元生成函数 ，只需得到 的各项系数，就能完成任务。

例如如下递推式 其中 ，计算得 计算多项式 exp 即可，复杂度 。

如果 较为复杂， 可能难以计算。

系数和行列均有关的二维递推

欧拉数

从递推式入手求一行欧拉数。

记 ，则

考虑使用附加因子法将 合并，可以预见到，由于系数和行有关，所采用的附加因子不可能是常多项式，而是和所在行有关。因此，采用一阶 ODE 配凑并不能一劳永逸地解决问题，不过，我们可以先尝试一下。

计算附加因子 ，则有 不难想到简单配凑（将 除过去） 其中 。真是天造地设， 的递推已经容易解决。

，根据 ，可得 。

由 ，容易一次卷积计算一行欧拉数。