考虑一个合法序列的生成过程:依次考虑 $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

分类: 文章

Qiuly

QAQ

1 条评论

GalaxyOier · 2022年9月18日 11:39 上午

orz

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。

*

code