「Summary」EGF?

咕咕咕。

一些前置内容后续会写在Generating Function Editor里面，我先做一会鸽子题。

UOJ 449

所有鸽子都饱了显然不好处理，首先Min-Max容斥把它转化成求某个集合里面第一次有鸽子吃饱。

观察到所有鸽子都是等价的，所以只有鸽子集合的大小是有用的。于是形式化一点，设 $g_m$ 表示对于一个大小为 $m$ 的鸽子集合，其中第一只鸽子被喂饱的期望步数，此处的步数指小 Z 投放玉米到这个集合的次数，有

$$ \begin{aligned} res = \sum_{m = 1}^{n} (-1)^{m + 1} \binom{n}{m} g_m \end{aligned} $$

注意不要忘记乘组合数 $\binom{n}{m}$。

现在思考如何计算 $g_m$，首先计算出小 Z 投 $i$ 次玉米到该集合中的期望步数。投入一次的概率是 $\frac{m}{n}$，期望是 $\frac{n}{m}$。于是投 $i$ 次的期望是 $i\frac{n}{m}$。
考虑对投入的每一颗玉米标号，标记它被投放给了哪一只鸽子，记这个序列为 $c$，即是说 $c_i$ 表示第 $i$ 颗玉米投放给的鸽子标号。
那么这个序列的期望长度就是 $g_m$，序列停止变长的条件是某一只鸽子吃饱了。记序列长度为 $len$,可以发现一定是 $c_{len}$ 吃饱了，因为鸽子等价，只需要考虑 $1$ 号鸽子吃饱的情况就行了。
这个序列在结束是会满足如下条件：

• $1$ 出现了恰好 $k$ 次，并且该序列最后一个数为 $1$。
• 其余所有数出现次数小于 $k$，并且不能是该序列最后一个数。

对序列计数的常用手段是EGF。
$1$ 的生成函数是 $\frac{x^{k - 1}}{(k - 1)!}$，其余的数的生成函数都是 $\sum_{i = 0}^{k - 1} \frac{x^i}{i!}$。
答案的生成函数即是

$$ \begin{aligned} \frac{x^{k - 1}}{(k - 1)!} \left( \sum_{i = 0}^{k - 1} \frac{x^i}{i!} \right)^{m - 1} \end{aligned} $$

最后的出来的 $[x^{i - 1}]\frac{x^{k - 1}}{(k - 1)!} \left( \sum_{i = 0}^{k - 1} \frac{x^i}{i!} \right)^{m - 1}$ 即是长度为 $i$ 的序列的数量的 $\frac{1}{m}$。

记 $f(x) = \sum_{i = 0}^{k - 1} \frac{x^i}{i!}$，即是要求 $\frac{x^{k - 1}}{(k - 1)!}f^{m - 1}_{(x)}$ 的各项系数。

然后需要对幂级数求导，有 $\color{red} f'(x) = f(x) - \frac{x^{k - 1}}{(k - 1)!}$。

$$ \begin{aligned} \left( f^m \left( x \right) \right)' &= m \cdot f^{m-1} \left( x \right) \cdot f' \left( x \right) \\ &= m \cdot f^{m-1} \left( x \right) \cdot \left( f \left( x \right) - \frac {x^{k - 1}} {\left( k - 1 \right) !} \right) \\ &= m \cdot \left( f^m \left( x \right) - \frac {x^{k - 1}} {\left( k - 1 \right) !} f^{m-1} \left( x \right) \right) \end{aligned} $$

于是有

$$ \begin{aligned} i \cdot \left[ x^i \right] f^m \left( x \right) = m \cdot \left( \left[ x^{i-1} \right] f^m \left( x \right) - \left[ x^{i-1} \right] \frac {x^{k - 1}} {\left( k - 1 \right) !} f^{m-1} \left( x \right) \right) \end{aligned} $$

于是可以递推求。

那么最后对于一对 $(m, i)$ 贡献就为

$$ \begin{matrix} m \cdot \left( i - 1 \right) ! \left[ x^{i-1} \right] \left( \frac {x^{k - 1}} {\left( k - 1 \right) !} \cdot f^{m-1} \left( x \right) \right) \cdot \frac 1 {m^i} \cdot i \cdot \frac nm \\ = i ! \left[ x^{i-1} \right] \left( \frac {x^{k - 1}} {\left( k - 1 \right) !} \cdot f^{m-1} \left( x \right) \right) \cdot \frac n {m^i} \end{matrix} $$

UOJ514

首先转化问题允许向吃饱的鸽子投玉米，这样可以投玉米的概率一直都不会变。
问题变成求所有鸽子吃饱之后有一只吃撑的概率 $p$，最后的结果为 $np$。

定义 $p_m$ 表示集合大小为 $m$ 中 $1$ 号鸽子吃撑的时候其它所有鸽子都没有饱的概率。
那么答案是

$$ \begin{aligned} res = n\sum_{i = 2}^{n}(-1)^{i}\binom{n - 1}{i - 1} p_{i} \end{aligned} $$

仿照上一题的思路，把它转化为求序列方案数。
考虑对投入的每一颗玉米标号，标记它被投放给了哪一只鸽子，记这个序列为 $c$，即是说 $c_i$ 表示第 $i$ 颗玉米投放给的鸽子标号。

• $1$ 出现了恰好 $a$ 次，并且该序列最后一个数为 $1$。
• 其余所有数出现次数小于 $b$，并且不能是该序列最后一个数。

于是就和上一题几乎一样了，再写一遍加深印象。

生成函数为
$$ \begin{aligned} \frac{x^a}{a!} \left(\sum_{i = 0}^{b - 1}\frac{x^i}{i!}\right)^{m - 1} \end{aligned} $$

然后开导，记 $f(x) = \sum_{i = 0}^{b - 1} \frac{x^i}{i!}$，导出来得到 $f'(x) = f(x) - \frac{x^{b - 1}}{(b - 1)!}$。
再导一次

$$ \begin{aligned} (f^{m}(x))' &= m \cdot f^{m - 1}(x) f'(x) \\ &= m \cdot f^{m - 1}(x) \left(f(x) - \frac{x^{b - 1}}{(b - 1)!}\right) \\ &= m \cdot \left(f^{m}(x) - \frac{x^{b - 1}}{(b - 1)!} f^{m - 1}(x) \right) \end{aligned} $$

直接递推解决。

最后对于每一对枚举的 $(m, i)$，合法序列个数为 $(i - 1)![x^{i - 1}]\left( \frac{x^a}{a!} f^{m - 1}(x) \right)$，概率为 $\frac{1}{m!}$。