题解 CF1349F Slime and Sequences
gxy001
·
·
个人记录
好神仙啊。
对于任何一个好序列 a，可以通过这样的方式把它转化为一个排列 p：先倒着列出 1 的出现位置，然后倒着列出 2 的出现位置，如此类推。
我们发现，一个排列和一个好的序列一一对应，第 p_i 个位置的值为 p_1,\cdots,p_i 间的升高数加一。
设答案为 f_{0,\cdots,n-1}，则有：
f_k=\sum\limits_{i=1}^n\left<\begin{matrix}i\\k\end{matrix}\right>\begin{pmatrix}n\\i\end{pmatrix}(n-i)!
这样 F1 就做完了。
我们注意到复杂度瓶颈在欧拉数的计算，至少有 k 次升高的方案数为 n^{n-k}（钦定 k 个位置填 <，小于号连接的部分称为一段，则总共有 n-k 段，一段的 \text{EGF} 为 e^x-1，即一个非空集合），那么欧拉数就有
\left<\begin{matrix}n\\k\end{matrix}\right>=\sum\limits_{i=k}^n\begin{pmatrix}i\\k\end{pmatrix}(-1)^{i-k}n^{n-i}
则有
\begin{aligned}
f_k=&\sum\limits_{i=1}^n\sum\limits_{j=k}^i\begin{pmatrix}j\\k\end{pmatrix}(-1)^{j-k}i^{i-j}\begin{pmatrix}n\\i\end{pmatrix}(n-i)!\\
=&\frac{n!}{k!}\sum\limits_{i=1}^n\sum\limits_{j=k}^i\frac{j!(-1)^{j-k}}{(j-k)!}[x^i](e^x-1)^{i-j}\\
=&\frac{n!}{k!}\sum\limits_{j=k}^n\frac{j!(-1)^{j-k}}{(j-k)!}\sum\limits_{i=j}^n[x^i](e^x-1)^{i-j}\\
\end{aligned}
注意到如果设 g_j=\sum\limits_{i=j}^n[x^i](e^x-1)^{i-j}，上面这个东西就很好计算了。
这样复杂度瓶颈在求出 g，继续推式子。
\begin{aligned}
g_j&=\sum\limits_{i=j}^n[x^i](e^x-1)^{i-j}\\
&=[x^j]\sum\limits_{i=j}^n(\frac{e^x-1}{x})^{i-j}\\
&=[x^j]\sum\limits_{i=0}^{n-j}(\frac{e^x-1}{x})^i\\
&=[x^j]\frac{1-(\frac{e^x-1}{x})^{n-j+1}}{1-\frac{e^x-1}{x}}\\
&=[x^j]\frac{1}{1-\frac{e^x-1}{x}}-[x^j]\frac{(\frac{e^x-1}{x})^{n-j+1}}{1-\frac{e^x-1}{x}}\\
\end{aligned}
下面使用 F(x)=\frac{e^x-1}{x}。
第一部分直接多项式求逆，[x^j]\frac{1}{1-F(x)}=[x^j]\frac{x^{-1}}{x^{-1}(1-F(x))}=[x^{j+1}]\frac{1}{x^{-1}(1-F(x))}。
后面部分 [x^j]\frac{F(X)^{n-j+1}}{1-F(x)}=[x^{n+1}]\frac{(xF(x))^{n-j+1}}{1-F(x)}。
我们用一种神仙做法——加一个元以区分信息，那么这个东西就等价于 [x^{n+1}y^{n-j+1}]\sum\limits_{i=0}^\infin\frac{(xF(x)y)^i}{1-F(x)}=[x^{n+1}y^{n-j+1}](\frac{1}{1-F(x)}\frac{1}{1-xF(x)y})。
设 W(x)=xF(x)=e^x-1，H(x) 满足 \frac{W(x)}{H(W(x))}=x，\frac{F(x)}{H(W(x))}=1，即 F(x)=H(W(x))。
设 G(x)=\frac{1}{1-H(x)}\frac{1}{1-xy}，那么我们求的就是 [x^{n+1}]G(W(x))。
设 P(x) 为 W(x) 的复合逆，根据扩展拉格朗日反演得，[x^{n+1}]G(W(x))=\frac{1}{n+1}[x^n]G'(x)(\frac{x}{P(x)})^{n+1}。
所以我们要求的实际上是 $\frac{1}{n+1}[x^ny^{n-j+1}]\frac{y(1-H(x))+H'(x)(1-xy)}{(1-H(x))^2(1-xy)^2}H(x)^{n+1}$。
$$
\frac{1}{n+1}[x^ny^{n-j+1}]\frac{y(1-H(x))+H'(x)(1-xy)}{(1-H(x))^2(1-xy)^2}H(x)^{n+1}\\
=\frac{1}{n+1}[x^ny^{n-j+1}](\frac{1}{(1-H(x))}\sum\limits_{i=0}^\infin (i+1)x^iy^{i+1}+\frac{H'(x)}{(1-H(x))^2}\sum\limits_{i=0}^\infin x^iy^i)H(x)^{n+1}\\
=\frac{1}{n+1}[x^n](\frac{1}{(1-H(x))}(n-j+1)x^{n-j}+\frac{H'(x)}{(1-H(x))^2}x^{n-j+1})H(x)^{n+1}\\
=\frac{1}{n+1}((n-j+1)[x^j]\frac{H(x)^{n+1}}{(1-H(x))}+[x^{j-1}]\frac{H'(x)H(x)^{n+1}}{(1-H(x))^2})\\
=\frac{1}{n+1}((n-j+1)[x^{j+1}]\frac{H(x)^{n+1}}{x^{-1}(1-H(x))}+[x^{j+1}]\frac{H'(x)H(x)^{n+1}}{x^{-2}(1-H(x))^2})\\
$$
就可以直接算了。
```cpp
```