P5162 WD与积木
省略及其冗长难懂的题面，给出形式化题面：对于序列 \(\{1, 2, 3, \dots, n\}\)，将它分到若干个非空集合中，然后将这些非空集合排成一列。
求所有方案中集合的个数和除以总方案数。
我觉得这题最难的是看懂题。
直接把分子分母分开算。先考虑分母。
有标号，所以用 EGF 做。
显然一个非空集合的 EGF 是 \(e^x - 1\)。
然后集合是有序的。
所以是个幂级数。化简完后是
\[\frac 1{2 - e^x} \]然后就把分母的 EGF 搞出来了。
分子呢？
集合数量的和。
首先每个非空集合提供的集合数量是 \(1\)，EGF 还是 \(e^x - 1\)。
枚举集合数量
\[\sum _{k} k(e^x - 1) ^ k \]要推这个玩意的封闭形式了。
换元 \(z = (e^x - 1) ^ k\)
\[\sum_k kz^k \]这玩意看起来可以看成是 \(\{0, 1, 2, \cdots\}\) 的 OGF。
前面那玩意是 \(\frac 1 {1 - z}\) 的累计求和右移一位，所以看起来是
\[\frac z {(1 - z) ^ 2} \]把 \(z\) 代回去
\[\frac {e^x - 1} {(2 - e^x) ^ 2} \]然后直接除一下。
做完了？
做完了。
要是我早把题看懂我早就做完了（暴论
但其实不是，在换元那一步卡了一会。
标签：WD,frac,积木,空集合,集合,EGF From： https://www.cnblogs.com/AzusidNya/p/18248764