考虑一个合法序列的生成过程：依次考虑 i:[1,n]，将 i 插入序列中。因此，我们考虑如下生成方式：依次考虑 i:[1,n]，再考虑一个未被加入的位置集合的子集 T，将 T 从大到小排序插入到序列 q 末尾。
我们钦定 q 满足如下要求：对于 i 选中的 T 和 i−1 选中的 T′，maxT>minT′ 。此时 q 与 p 一一对应，我们只需要考虑 q 的问题。
我们可以形象化地将 q 看成若干递增子段拼合而成，而每一个子段对应一个 i 。因此，为了方便，我们设 d(i,j) 表示长度为 i 的段，钦定 j 个空隙插入小于号的方案数。将钦定小于号的空隙两旁的位置合并，容易得到：
d(i,j)=ii−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} 也是容易求的。
1 条评论
GalaxyOier · 2022年9月18日 11:39 上午
orz