CF1349D Slime and Biscuits

题意：有 个人，第 个人有 个饼干。

每次随机选择一个饼干，将其随机分配给除了它现在所有者的其他 个人。

求使得一个人拥有所有饼干的期望步数。

答案对 取模，，饼干总数，时限 。

---

好的期望题。设：

• 为游戏以 结束的概率。
• 为以 结束的所有情况，耗时乘发生概率的和。
• 为当饼干全在 手里才结束（全在其他某人手里不结束），所需的的期望步数。

注意 并非期望，只是期望的“一部分”，因为 而单个 一般小于 。 即为答案。

怎么在 和 之间转化呢? 考虑挖掉 中多余的贡献。

能发现，若所有饼干到达 之前，曾经一起到达过 ，此时游戏早该结束了，于是导致了不合法。

枚举游戏真正的结束位置，可得

其中 为小饼干全在 手中变为全在 手中（）所需的期望步数，不难发现这是一个常数。

移项得

对于将 ，将所有等式相加，可得 求出 之后即可得到答案。

---

求解 时，问题大大简化，对于单个 ，我们只在乎小饼干是否在 手中。

设 为 有 个小饼干仍需的期望步数。 为饼干总数。

每一步操作分三类讨论：

• 其他人给了其他人
• 其他人给了
• 给了其他人

可以得到：

边界条件是 。

---

如果我们直接根据这个关系式来消元，可能出现系数为 的情况，较难处理。

注意到，由于我们分类的组合意义，右侧 的系数（概率）和为 。（左侧显然也是 ，这样就可以对消了）

考虑（看官方题解）求 的递推式。

令 ，有 (注意是后缀和)。

是两侧共有的，可以消去。

现在只剩两项，可以直接递推了。整理得：

当 时可以得到边界：

最后，各个 就可以直接使用 得到。而 。