自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 22:45:07，当前版本为作者最后更新于2023-01-29 11:07:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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)$），因为我们已有牛顿迭代或半在线卷积方法。
$G \to H$ 的变换，无非就是 $H_{n_0}(x) = G_{n_0}(u^{\langle -1\rangle})$，而复合逆是易求的，且 $G_{n_0}$ 的形式是初等的。
$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 的修改日期。
• 接上条。当时这个问题其实是 tommymio (a. k. a. tommy0103) 在推导一道斯特林数问题时列出的错误递推式，当时 rqy 与 EI 在 U 群中进行了这一基变换的介绍，事后我也与 EI 进行了更深入的讨论（翻译：我看不懂然后去找 EI 问），并向 tommy 进一步解释了做法（也不知道 tommy 有没有弄懂）。
• Wikipedia. Eulerian numbers of the second order。

此外，事实上这一基变换本质上是对转移矩阵进行了对角化。而我们用幂级数方法快速执行了前后的线性变换。
我实现了一份 $O(n\log^2n/\log\log n)$ 的代码，似乎跑得比 std 快。