Coupons

题意概述

一共有$n$种不同的优惠券,每次得到每种优惠券的概率相同。问期望多少次可以得到所有种类的优惠券,以带分数形式输出。
数据范围:$1 \le n \le 33$。

算法分析

假设当前已经有$k$种优惠券,那么获得新优惠券的概率是${n-k \over n}$,所以需要步数的期望是${n \over n-k}$。求和得到总步数的期望是${n \over n}+{n \over n-1}+{n \over n-2}+…+{n \over 1}=n\sum_{i=1}^n{1 \over i}$。

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *