收集邮票（神仙概率）

题意：有n种邮票，等概率购买，买第k次k元，求集齐邮票所需钱的的期望概率

用$f[i]$表示现在取到$i$张邮票,要取完剩下邮票的期望次数

$$f(i)=\frac{i}{n}f(i)+\frac{n-i}{n}f(i+1)+1\\ f(i)=f(i+1)+\frac{n}{n-i}\\ f(n)=0$$

1

用$g[i]$表示现在取到$i$张邮票,要取完剩下邮票的期望价格。

若邮票初始购买需要1元(就是$f(i)$)，当你购买完一个邮票时,之后的所需价值都加1,则此时那么后面需要加1的邮票数就是所需的期望天数喽

$$g(i)=\frac{i}{n}(g(i)+f(i))+\frac{n-i}{n}(g(i+1)+f(i+1))+1(1就是邮票初始值)\\ g(i)=g(i+1)+f(i+1)+1+\frac{i}{n-i}f(i)+\frac{n}{n-i}\\ g(n)=0$$

2

若买了$k$张邮票

$$money=(k^2+k)/2$$

则求$E(money)$

$$f(i)\\ g(i)=f(i^2)（注意，这个是平方的期望，不等于期望的平方！！）\\ g((i+1))=f((i+1)^2)=g(i)+2f(i)+1\\ E(money)=\frac{f(0)+g(0)}{2}$$