Description：

有 $n$ 种不同的邮票，每次只能买一张，买到的邮票是 $n$ 种邮票中的哪一种是等概率的，均为1/n，购买第k张邮票需要支付k元钱。求得到所有种类的邮票需要花费的钱数目的期望。

$1\le n \le 10000$

Solution：

如果每次买邮票都只花 $1$ 元，设 $f[i]$ 为已经买了 $i$ 种邮票，买完 $n$ 种邮票还要的期望次数。

则有： $f[i]=\frac i n (f[i]+1)+\frac {n-i} n(f[i+1]+1)$ 。

大概就是 $i$ 这个点有 $\frac i n$ 的概率走自环，有 $\frac {n-i}n$ 的概率走到 $i+1$ 。

整理得： $f[i]=f[i+1]+\frac n {n-i}$

如果第 $i$ 次是 $i$ 元，则答案为 $E(\frac {k(k+1) } 2)$ ，由期望的线性性质，得 $E(\frac {k(k+1) } 2)=\frac 1 2(E(k^2)+E(k))$

于是只要处理平方的期望即可，但平方的期望不等于期望的平方。

让 $g[i]$ 表示已经收集了 $i$ 张到收集完 $n$ 张的步数平方的期望。

$g[i]=\frac i n\times E((f[i]+1)^2 )+\frac {n-i} n\times E((f[i+1]+1)^2 )=\frac i n×(g[i]+2f[i]+1)+\frac {n-i} n\times(g[i+1]+2f[i+1]+1)$

整理得： $g[i]=\frac i {n-i}(2f[i]+1)+g[i+1]+2f[i+1]+1$

最终答案为 $\frac 1 2(g[0]+f[0])$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 10010

double g[MAXN],f[MAXN];

int main()

{

	scanf("%d",&n);

	f[n] = 0;g[n] = 0;

	for(int i = n - 1;i >= 0;--i)

	{

		f[i] = f[i + 1] + (double)n / (double)(n - i);

		g[i] = (double)i / (double)(n - i) * (2 * f[i] + 1) + g[i + 1] + (double)2 * f[i + 1] + (double)1;

	}

	printf("%.2lf\n",(g[0] + f[0]) / (double)2);

	return 0;

}