求解迭代列的一些手法
Aleph1022
·
·
个人记录
例 1
\left\{
\begin{aligned}
F_k(x) &= (k - 1) F_{k-1}(x) + (k - 1) x F_{k-2}(x) \\
F_0(x) &= 1
\end{aligned}
\right.
给定 c_0, \dots, c_n，求解 \sum_{k=0}^n c_k F_k(x)。
将迭代写作矩阵的形式
\begin{pmatrix}
F_k(x) \\ F_{k-1}(x)
\end{pmatrix} = \begin{pmatrix}
k-1 & (k-1)x \\
1 &
\end{pmatrix} \begin{pmatrix}
F_{k-1}(x) \\ F_{k-2}(x)
\end{pmatrix}
分治计算即可。
时间复杂度 \Theta(n \log^2 n)。
例 2
给定 $d_0, \dots, d_m$，对于 $k = 0, \dots, n$ 求解 $\sum_{j=0}^m d_j [x^j] F_k(x)$。
---
这是上一个问题的转置。
时间复杂度 $\Theta(n \log^2 n)$。
## 例 3
$F_k(x)$ 的定义同上例。
求解 $F_n(x)$，要求做到 $\Theta(n \log n)$。
---
我们考虑通过微分方程求解其封闭形式。
一般来说，选择 EGF 或者 OGF 大概需要通过尝试，或是通过组合意义判断。
设 $F(x, t) = \sum_{k\ge 0} F_k(x) \frac{t^k}{k!}$，有
$$
\begin{aligned}
F_k(x) &= (k - 1) F_{k-1}(x) + (k - 1) x F_{k-2}(x) \\
\frac{F_k(x)}{(k-1)!} &= \frac{F_{k-1}(x)}{(k-2)!} + x \frac{F_{k-2}(x)}{(k-2)!} \\
[t^{k-1}] (1-t)\frac{\partial}{\partial t} F(x,t) &= [t^{k-1}] xt F(x, t) \\
\frac{\partial}{\partial t} F(x,t) &= \frac{xt}{1-t} F(x, t) \\
F(x, t) &= \mathrm e^{\int \frac{xt}{1-t} \,\mathrm dt} \\
&= C \mathrm e^{x\left(\ln\frac1{1-t}-t\right)} \\
&= \mathrm e^{x\left(\ln\frac1{1-t}-t\right)} \qquad (F(x,0) = 1)
\end{aligned}
$$
即得 $[x^j] F_n(x) = \left[\frac{t^n}{n!}\right] \frac{\left(\ln\frac1{1-t}-t\right)^j}{j!}$。
这是一个可以用 Lagrange 反演解决的[经典问题](https://www.luogu.com.cn/blog/NaCly-Fish-blog/a-classical-problem)。借助 Newton 迭代，我们容易在给定的复杂度内解决问题。
## 例 4
$$
\left\{
\begin{aligned}
F_k(x) &= (1+x)(F_{k-1}(x)+x^2F_{k-1}'(x)) \\
F_0(x) &= 1
\end{aligned}
\right.
$$
给定 $c_0, \dots, c_n$，求解 $\sum_{k=0}^n c_k F_k(x)$。
---
现在开始有微分了。
我们先展开为递推式观察，有
$$
F_{k,j} = F_{k-1,j} + jF_{k-1,j-1} + (j-2)F_{k-1,j-2}
$$
不妨对列建立 GF，得迭代
$$
\left\{
\begin{aligned}
\widehat F_j(t) &= \frac{jt}{1-t} \widehat F_{j-1}(t) + \frac{(j-2)t}{1-t} \widehat F_{j-2}(t) \\
\widehat F_0(t) &= \frac1{1-t}
\end{aligned}
\right.
$$
类似例 1，将迭代写作矩阵，然后将分治算法转置即可。
时间复杂度 $\Theta(n \log^2 n)$。
## 例 5
$$
\left\{
\begin{aligned}
F_k(x) &= F_{k-1}'(x) + A(x) F_{k-1}(x) \\
F_0(x) &= B(x)
\end{aligned}
\right.
$$
其中 $A(x), B(x)$ 为不超过 $m-1$ 次多项式。
求 $F_n(x) \bmod x^m$。
---
了解一阶线性 ODE 通解的读者可能容易想到做变换 $G_k(x) = \mathrm e^{\int A(x) \,\mathrm dx}F_k(x)$，其中常数取 $0$ 即可。
于是迭代变为
$$
\left\{
\begin{aligned}
G_k(x) &= G_{k-1}'(x) \\
G_0(x) &= \mathrm e^{\int_0^x A(t) \,\mathrm dt}B(x)
\end{aligned}
\right.
$$
可得 $F_n(x) = \mathrm e^{-\int_0^x A(t) \,\mathrm dt} G_0^{(n)}(x)$。
时间复杂度 $\Theta((n+m) \log (n+m))$。
## 例 6
$$
\left\{
\begin{aligned}
F_k(x) &= \frac x{1-x}F_{k-1}'(x) + F_{k-1}(x) \\
F_0(x) &= \frac1{1-x}
\end{aligned}
\right.
$$
求解 $[x^m] F_n(x)$。$n$ 非常大。
---
这个迭代并不容易用附加因子的方法来化简，但我们考虑 $G_k(x) = x G_{k-1}'(x) + G_{k-1}(x)$ 的形式是容易解决的。
接下来我们引入另一种手法：换元。EI 叫它**基变换换元**。设 $F_k(x) = G_k(u)$，有
$$
\begin{aligned}
G_k(u(x)) &= u(x) G_{k-1}'(u(x)) + G_{k-1}(u(x)) \\
&= \frac{u(x)}{u'(x)} [G_{k-1}(u(x))]' +G_{k-1}(u(x))
\end{aligned}
$$
解 $\frac{u(x)}{u'(x)} = \frac x{1-x}, u(0)=0$ 得 $u(x) = x \mathrm e^{-x}$，我们有
$$
\left\{
\begin{aligned}
G_k(u) &= u G_{k-1}'(u) + G_{k-1}(u) \\
G_0(u) &= \frac1{1-(u\mathrm e^{-u})^{\langle-1\rangle}}
\end{aligned}
\right.
$$
则
$$
\begin{aligned}
[x^m] F_n(x) &=
[x^m] G_n(u(x)) \\
&= [x^m] \sum_{j\ge 0} (x\mathrm e^{-x})^j [u^j] G_n(u) \\
&= \sum_{j\ge 0} \frac{(-j)^{m-j}}{(m-j)!} [u^j] G_n(u) \\
&= \sum_{j\ge 0} \frac{(-j)^{m-j}(j+1)^n}{(m-j)!} [u^j] G_0(u) \\
\end{aligned}
$$
有显然的 $\Theta(m \log m + m \log_m n)$ 做法。
也可以做到 $\Theta(m + m \log_m n)$，留作读者练习。
## 例 7
$$
\left\{
\begin{aligned}
F_k(x) &= (x^2-1)F_{k-1}'(x) \\
F_0(x) &= x
\end{aligned}
\right.
$$
给定 $x_0$，求解 $F_0(x_0), \dots, F_n(x_0)$。
---
运用例 4 的方法，可以在 $\Theta(n\log^2 n)$ 的时间内求解稍微一般一点的问题。
我们考虑继续使用基变换换元。
由于我们通常希望 $\operatorname{ord} u(x)=1$，这次我们的目标应该设为 $G_k(u) = G_{k-1}'(u)$（设为 $G_k(u) = u G_{k-1}'(u)$ 也可以完成推导，但不太符合计算上的直觉）。
求解 $\frac1{u'(x)} = x^2-1, u(0)=0$ 得 $u(x) = \frac12 \ln \frac{1-x}{1+x}$，我们有迭代
$$
\left\{
\begin{aligned}
G_k(u) &= G_{k-1}'(u) \\
G_0(u) &= \frac{1-\mathrm e^{2u}}{1+\mathrm e^{2u}}
\end{aligned}
\right.
$$
记 $u_0 = u(x_0)$，我们希望求得 $G_0(u_0), \dots, G_0^{(n)}(u_0)$。
根据 Taylor 展开，只需求出 $G_0(u+u_0)$ 的前 $n+1$ 项系数即可。若加以整理亦可以得到官方题解中给出的二元 GF 的封闭形式。
时间复杂度 $\Theta(n \log n)$。
## 结语
经过总结不难发现我们目前对迭代列大致有四种手法：
1. 分治计算矩阵积，亦可结合转置原理。
1. 附加因子化简微分。
1. 基变换换元化简微分。
1. 解（偏）微分方程获得封闭形式。
在解出迭代列后，有时也需要一些别的计算手段（例如：[小 Q 的序列](https://loj.ac/p/6703)使用多点求值），使得这类问题往往难以一眼看穿复杂度（？）。
其中解微分方程的方法，尤其是涉及多个元的偏微分方程，由于分析方法较为深刻，我们通常不会去使用（然而例 7 的官方题解使用了此方法）。
而附加因子与基变换换元的方法也有一些局限：我们难以准确地选择合适的方法将问题改写为迭代列形式，有时需要一定的尝试和组合观察。
事实上，这类问题蕴含的内涵仍然十分深刻，笔者也仅能（在 EI 的帮助下）窥其一二。
## 参考资料
1. [那些你不要的（1）2021.4.27 ~ 2021.6.12](https://blog.csdn.net/EI_Captain/article/details/118074883) 及其历史版本（例 4, 6）。
1. [Feux Follets](https://www.luogu.com.cn/problem/P7440) 及其[弱化版](https://www.luogu.com.cn/problem/P7439)（例 1, 2, 3）。
1. [2022 杭电多校 Round 6 C](https://qoj.ac/contest/973/problem/4491?v=1)（例 5）。
1. 2023 牛客多校 Round 10 H（例 7）。
1. Private conversation with tommymio / tommy0103（例 6）（详见[此文章](https://www.luogu.com.cn/blog/your-alpha1022/yet-another-eulerian-number-problem-qiu-xie-han-wei-fen-di-die-dai-li)）。
1. Private conversation with Elegia / EntropyIncreaser。