这个题实在是太棒了，让我忍不住想第一时间发出来。只能说 EI 总是能给我们带来一些惊喜。
以下内容参考自 EI 课件。
（但是知道 idea 来源之后似乎就没那么酷了）
简要题意.
对于正整数 \(\alpha\)，考虑下述长为 \(\alpha n\) 的序列 \(a\)：
- 对于每个 \(k = 1, \dots, n\)，序列 \(a\) 中出现了恰好 \(\alpha\) 个 \(k\)。
- 对于 \(i<j\) 满足 \(a_i=a_j\)，那么对任意 \(i<k<j\)，有 \(a_k \ge a_i\)。
我们称满足上述要求的序列是一个 \(n\) 阶的 \(\alpha\)-排列。现在输入一个 \(n_0\) 阶 \(\alpha\) 排列 \(P\)。又给定 \(n, m\)，请你计算有多少 \(n\) 阶 \(\alpha\)-排列包含子序列 \(P\)，并且满足：
- 总共有 \(m\) 个下标 \(i\) 满足 \(a_i > a_{i+1}\)。
只需计算出这样的序列总数对 \(998244353\) 取模的结果。
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 快。