【题解】CF1349F2 Slime and Sequences (Hard Version) 组合数学 / 多项式 / 扩展拉格朗日反演 — Qiuly

考虑一个合法序列的生成过程：依次考虑 $i:[1,n]$，将 $i$ 插入序列中。因此，我们考虑如下生成方式：依次考虑 $i:[1,n]$，再考虑一个未被加入的位置集合的子集 $T$，将 $T$ 从大到小排序插入到序列 $q$ 末尾。

我们钦定 $q$ 满足如下要求：对于 $i$ 选中的 $T$ 和 $i-1$ 选中的 $T’$，$\max T>\min T’$ 。此时 $q$ 与 $p$ 一一对应，我们只需要考虑 $q$ 的问题。

我们可以形象化地将 $q$ 看成若干递增子段拼合而成，而每一个子段对应一个 $i$ 。因此，为了方便，我们设 $d(i,j)$ 表示长度为 $i$ 的段，钦定 $j$ 个空隙插入小于号的方案数。将钦定小于号的空隙两旁的位置合并，容易得到：
$$
d(i,j)=i![x^{i}]{}(e^{x}-1)^{i-j}
$$
而对于 $i$ 的问题，考虑每个位置的贡献（注意到我们要求小于号个数恰好为 $i-1$）：
$$
\begin{aligned}
\mathbf {ans}(i) & = n!\sum_{p=1}^{n}\frac{1}{p!}\sum_{c=i-1}^{p-1}(-1)^{c-i+1}{c\choose i-1}d_{p,c}\\
&=\frac{n!}{(i-1)!(-1)^{i-1}}\sum_{p=1}^{n}[x^{p}]\sum_{c=i-1}^{p-1}\frac{(-1)^{c}c!}{(c-i+1)!}(e^{x}-1)^{p-c}\\
&=\frac{n!}{(i-1)!(-1)^{i-1}}\sum_{c=i-1}^{n-1}\frac{(-1)^{c}c!}{(c-i+1)!}\sum_{p=c+1}^{n}[x^p]{}(e^{x}-1)^{p-c}
\end{aligned}
$$
此时我们的目标变成了：对 $0\leq c<n$ 求 $\sum\limits_{p=c+1}^{n}[x^p]{}(e^{x}-1)^{p-c}$ 。此时：
$$
\begin{aligned}
\sum\limits_{p=c+1}^{n}[x^p]{}(e^{x}-1)^{p-c}&=[x^c]\sum\limits_{p=c+1}^{n}\left(\frac{e^{x}-1}{x}\right)^{p-c}\\
&=[x^c]\sum\limits_{p=1}^{n-c}\left(\frac{e^{x}-1}{x}\right)^{p}
\end{aligned}
$$
为了方便不妨令 $F(x)=\frac{e^{x}-1}{x}$，接着推：
$$
\begin{aligned}
{}[x^c]\sum\limits_{p=1}^{n-c}\left(\frac{e^{x}-1}{x}\right)^{p}&=[x^c]\frac{F(x)-F(x)^{n-c+1}}{1-F(x)}\\
&=[x^{c+1}]\frac{xF(x)}{1-F(x)}-[x^{n+2}]\frac{x(xF(x))^{n-c+1}}{1-F(x)}
\end{aligned}
$$
前半部分的多项式对每个 $c$ 都是固定的，而后半部分我们凑了一个 $x$ 使得询问的项对每个 $c$ 也是固定的。

对于后半部分，问题变成了：令 $F'(x)=\frac{x}{1-F(x)},G(x)=xF(x)=e^x-1$，对每个 $2\leq i\leq n+1$ 求 $[x^{n+2}]G(x)^iF'(x)$ 。考虑引入辅元 $u$ 求 $[x^{n+2}][u^i]\frac{F'(x)}{1-uG(x)}$，令 $P(x)=F'(G^{-1}(x))$，用扩展拉格朗日反演提取系数：
$$
[x^{n+2}]\frac{P(G(x))}{1-uG(x)}=\frac{1}{n+2}[x^{n+1}]\frac{(1-ux)P'(x)+uP(x)}{(1-ux)^2}\left(\frac{x}{G^{-1}(x)}\right)^{{n+2}}
$$
最后的任务只剩下求解 $G(x)^{-1}$ 和 $P(x)=F'(G(x)^{-1})$ 了。构造 $G(x)^{-1}=\ln(x+1)$ 即可，而对于 $F'(\ln(x+1))=\frac{\ln(x+1)}{1-F(\ln(x+1))}=\frac{\ln(x+1)^2}{\ln(x+1)-x}$ 也是容易求的。

提交记录：Submission #172105607 – Codeforces。