忘记同步更进了

前置知识

什么是数学期望？

类似于加权平均，离散型随机变量的一切可能的取值  与对应的概率  乘积之和称为该离散型随机变量的数学期望 。

因此， 可表示为：

分析

本题最大的特点是每个盘子中至多有  个寿司。

如果有两个盘子都有  个寿司，那么它们就没有区别。

也就是说，无论这两个盘子排在哪里，最终输出的答案是一致的。无端联想排列组合。

因此，我们只需要关心不同寿司个数的盘子的数量，这些盘子的顺序对最终答案没有任何影响。

实现

 表示当当前寿司数为  的盘子有  个，寿司数为  的盘子有  个，寿司数为  的步数为  个时，吃完全部所需的期望。

dp 方程如下：

显然，维度  具有单调性，因此  需要放在循环外层。

Code