---
title: Coupons
tags:
  - Probability
id: "226"
categories:
  - - OI
    - Number Theory
date: 2017-06-07 00:00:00
---

## 题意概述

一共有$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}+\cdots+{n \over 1}=n\sum_{i=1}^n{1 \over i}$。