Yet Another Eulerian Number Problem —— 求解含微分的迭代列一例

· · 题解

I

先考虑写如何暴力。

经典的做法往往是按大小插入，并且在题目限制下，这一过程是很顺利的。同时可以发现，我们只关心给出的 P 中有多少个 >，记为 m_0。

有 DP

F_{n, m} = (\alpha(n-1)+1-m) F_{n-1, m-1} + (m+1) F_{n-1, m}

初始条件是 F_{n_0, m_0} = 1。

那我们自然是忍不住先对行或列建立生成函数尝试一下。根据欧拉数的经验，以 F_n(x) 为一行的生成函数应该是更符合直觉的方向。

先列出迭代式 F_{n+1}(x) = (\alpha n x+1) F_n(x) + x(1-x)\frac{\mathrm d}{\mathrm d x} F_n(x)，但其不作一些变换是很难处理的，这一迷惑我们暂且搁置。

II

我们不妨先来观察 \alpha=1 的情形。考虑欧拉数的 BGF \frac{(1-t)\mathrm e^{x(1-t)}}{1-t\mathrm e^{x(1-t)}}，我们将其插入 n_0+1 个空隙当中，则总体的 GF 应为

\begin{aligned} &\quad\; \left[\left(\frac{(1-t)\mathrm e^{x(1-t)}}{1-t\mathrm e^{x(1-t)}}-1\right)t+1\right]^{n_0-m_0} \left(\frac{(1-t)\mathrm e^{x(1-t)}}{1-t\mathrm e^{x(1-t)}}t\right)^{m_0}\frac{(1-t)\mathrm e^{x(1-t)}}{1-t\mathrm e^{x(1-t)}} \\ &= \left(\frac{1-t}{1-t\mathrm e^{x(1-t)}}\right)^{n_0-m_0} \left(\frac{t(1-t)\mathrm e^{x(1-t)}}{1-t\mathrm e^{x(1-t)}}\right)^{m_0}\frac{(1-t)\mathrm e^{x(1-t)}}{1-t\mathrm e^{x(1-t)}} \\ &= \frac{(1-t)^{n_0+1}t^{m_0}\mathrm e^{(m_0+1)x(1-t)}}{(1-t\mathrm e^{x(1-t)})^{n_0+1}} \end{aligned}

提取 [x^{n-n_0}/(n-n_0)!]，得

(1-t)^{n+1} \sum_{k\ge 0} (k+1)^{n-n_0} \binom{k-m_0+n_0}{n_0} t^k

为方便，下文中记 t 为 x。

观察此式，我们有明显更好的迭代关系

\frac{xF_{n+1}(x)}{(1-x)^{n+2}} = x\frac{\mathrm d}{\mathrm d x} \frac{xF_n(x)}{(1-x)^{n+1}}

令 G_n = xF_n/(1-x)^{n+1} 就有

G_{n+1}(x) = x G_n'(x)

推广到 \alpha > 1，也就是 G_n = xF_n/(1-x)^{\alpha n+1}。我们将其代入先前的迭代

\frac{(1-x)^{\alpha(n+1)+1}}xG_{n+1}(x) = (\alpha n x+1) \frac{(1-x)^{\alpha n+1}}x G_n(x) + x(1-x)\left[\frac{(1-x)^{\alpha n+1}}x G_n(x)\right]'

化简得

G_{n+1}(x) = \frac x{(1-x)^{\alpha-1}} G_n'(x)

我们知道 \alpha=1 的时候这个 G_{n+1} = x G_n' 的迭代，其实就是给 G_{n_0} 点乘了 k^{n-n_0}。
于是我们考虑作基变换将问题转化到此。假设 H_n(u) = G_n(x) 且

H_{n+1}(u) = u H_n'(u)

这样的话，我们若能完成 G \to H 和 H \to G 的变换，就解决了这个问题。

于是我们考虑先解出 u，即

H_{n+1}(u(x)) = \frac{u(x)}{u'(x)} [H_n(u(x))]'

解 u = u' \frac{x}{(1-x)^{\alpha-1}} 即可。我们不必求解析解（尽管它就是 \exp\left(\int_0^x \frac{(1-t)^{\alpha-1}}t \mathrm dt\right)），因为我们已有牛顿迭代或半在线卷积方法。

$H \to G$ 的变换，我们不再有复合的直接计算方法，但注意到只需 $H_n(u) (1-x)^{\alpha n+1}$ 的一项系数，即 $\left[H_n(x) (1-u^{\langle -1\rangle})^{\alpha n+1}\right] \circ u$，那么施拉格朗日反演即可。 这里应该有一些花絮，大概藏在其游记中。这里就简单放出一些 Hints。 - [那些你不要的（1）2021.4.27 ~ 2021.6.12](https://blog.csdn.net/EI_Captain/article/details/118074883?spm=1001.2014.3001.5501) 的修改日期。 - 接上条。当时这个问题其实是 tommymio (a. k. a. tommy0103) 在推导一道斯特林数问题时列出的错误递推式，当时 rqy 与 EI 在 U 群中进行了这一基变换的介绍，事后我也与 EI 进行了更深入的讨论（翻译：我看不懂然后去找 EI 问），并向 tommy 进一步解释了做法（也不知道 tommy 有没有弄懂）。 - [Wikipedia. Eulerian numbers of the second order](https://en.wikipedia.org/wiki/Eulerian_number#Eulerian_numbers_of_the_second_order)。 此外，事实上这一基变换本质上是对转移矩阵进行了对角化。而我们用幂级数方法快速执行了前后的线性变换。 我实现了一份 $O(n\log^2n/\log\log n)$ 的代码，似乎跑得比 std 快。