UVA10288题解

Pwtking · 2023-04-24 17:23:37 · 题解

题目中让我们求集齐全部图案的期望次数。

提供两种思路：

Solution one：

一个结论：若一个事件的概率为 \frac{n-i}{n}，那么其期望值为 \frac{n}{n-i}。

所以题目可以理解为在选出 i-1 种不同图案的情况下选出 i 种图案的期望值，i=n 时为答案，即 \sum_{i=1}^{n} \frac{n}{n-i+1}。

Solution two：

设 f_{i} 为已选出 i 种不同图案，剩下仍需选择的次数的期望值，那么 f_{i} 既可由 f_{i} 转移过来，即再选一次仍选中了已有的图案，那么显然转移方程为 x=\frac{i}{n}\times (f_{i}+1) ，（其中 x 为选择期望次数，下同。）；同时 f_{i} 又可由 f_{i+1} 转移过来，即再选一次选择了不同图案，转移方程为 x=\frac{n-i}{n}\times (f_{i+1}+1) 。

总状态转移方程即为：f_{i}=\frac{i}{n}\times (f_{i}+1) +\frac{n-i}{n}\times (f_{i+1}+1)。