Uoj#449. 【集训队作业2018】喂鸽子

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

题意：共有 只鸽子，每秒等概率选择一只鸽子并给他一粒玉米。一只鸽子饱了当且仅当它吃了的玉米粒数量 。

求期望多少秒之后所有的鸽子都饱了。

，，时限 。

Min-Max 反演： 由于 是确定的，所以某个集合中至少有一个鸽子被喂饱的期望耗时（即 ）只与集合大小有关。

设 为 只鸽子，至少有一个被喂饱的期望耗时。则

其中有 是因为我们实际上每次有 的概率喂到 中指定的 只鸽子。

接下来的任务就是求 。

枚举 ，所有鸽子共被喂食 次时有某只鸽子被喂饱了。

其中：

  • 表示选出一只被喂饱的鸽子的方案数。
  • 表示所消耗的秒数。
  • 表示将前 次给指定鸽子的喂食，插入共 次喂食，且最后一次喂给指定鸽子的方案数。
  • 表示 只鸽子喂了 次没有一只被喂饱的方案数。
  • 对于任意一种给定的长为 的喂食方案，其出现概率都为 。

接下来的任务就是求 。

使用 ，一只不饱的鸽子的生成函数为 易知 注意到有 ， 共有 个状态。

可以使用 NTT 每次卷一个 来求出 ，复杂度 。

其他求和的复杂度不超过 。

注意到 的特殊性，可以用 D-finite 科技构造递推，把 去掉。 可以 递推了。