本来没有必要写的，但是其他题解基本不知道在干嘛，所以还是记录一下？
先 min-max 容斥，转为对所有 \(i\in [1,n]\)，求 \(f(i)\) 表示 \(i\) 个鸽子中首次有鸽子吃 \(\ge k\) 个玉米的期望时间。
期望转概率，这样我们肯定要去设 \(f_{i,j}\) 表示 \(i\) 个鸽子吃了 \(j\) 个玉米还不存在鸽子吃 \(\ge k\) 个玉米的概率，然后再求和。
这里枚举第 \(i\) 个鸽子吃了几个然后做插入实在太烫了，平添复杂度吗这不是。
考虑 \(f_{i,j}\) 先从 \(f_{i,j-1}\) 继承，然后容斥掉此时恰好不合法的情形。那么我们先选择一个鸽子，令它于时刻 \(j\) 恰好吃了 \(k\) 个玉米，然后钦定它在序列中的位置，贡献系数为 \(i\times \binom{j-1}{k-1}\times (\frac{1}{i})^k\)，从 \(f_{i-1,j-k}\) 转移，这样就完了，吗？
哦不，这样过不了手造的小样例，这是因为忘算了剩余的 \(i-1\) 个鸽子的系数，它们所在的位置需要强制在 \(i\) 个鸽子中的 \(i-1\) 个选，所以还有一个 \((\frac{i-1}{i})^{j-k}\)。
所以得到了总转移式：
\[f_{i,j}=f_{i,j-1}-i\binom{j-1}{k-1}(\frac{1}{i})^k(\frac{i-1}{i})^{j-k}f_{i-1,j-k}
\]
\[Ans=\sum_{i=1}^{n}(-1)^{i+1}\binom{n}{i}\frac{n}{i}(\sum_{j=0}^{ik}f_{i,j})
\]
时空复杂度均能做到 \(O(n^2k)\)。