Uoj#514. 【UR #19】通用测评号

发表于 更新于 分类于 ， ， 阅读次数：

题意 : 有 个变量，初始值为 。

每次随机选择一个 的变量，将其加一。直到所有变量 为止。

求该过程结束后 的变量的期望个数。

，时限 。

随机过程中，可供选择的变量在变化，难以考虑。

不难发现，答案和操作总个数无关，我们可以把规则稍微改一下 ：

每次随机选择变量 ,直到所有变量 为止。求过程结束后 的变量的期望个数。

这个套路被戏称为“鞭尸”，原因可见：Luogu5644 [PKUWC2018]猎人杀。

我们称 的变量为满变量， 为半满变量。

除此之外，能够发现各个变量的地位都是平等的。

那么不妨求出操作结束时第一个变量 的概率，即第一个变量达到 时仍有变量 的概率。乘以 即为答案。

考虑容斥，钦定 个变量 ，设概率为 。特殊地，。

接下来，将每次操作的变量编号写成一个序列。只需要考虑 个被钦定的不半满变量和一个必须满的变量。

变成这样的问题：一个序列，值域为 ，要求 恰好出现 次，且最后一个必须是 ，其余的数出现 次。

不半满的 EGF： 。

钦定 最后达到全满，需要把前 次操作掺入，生成函数为 。

最后在操作序列末端手动加入一个填满操作，不方便用 描述，后面再处理。

最终的 EGF 为

任意一个长度为 的操作序列出现的概率为 。

则有 这里指数是 是因为后面加了一个填满操作。

最后进行容斥，设 为最后恰好有 个变量 的概率。

问题只剩求出各个 。用类似 Uoj#449 的方法（微分递推）计算 即可做到 。