收集邮票
题目描述
有 \(n\) 种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是 \(n\) 种邮票中的哪一种是等概率的，概率均为 \(1/n\)。但是由于凡凡也很喜欢邮票，所以皮皮购买第 \(k\) 次邮票需要支付 \(k\) 元钱。
现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。
输入格式
一行，一个数字 \(N\)（\(N \le 10000\)）。
输出格式
输出要付出多少钱，保留二位小数。
样例 #1
样例输入 #1
3
样例输出 #1
21.25
题解
首先明确：设抽\(k\)次需要的代价：\(\sum_{i=0}^ki=\frac{k^2+k}{2}\)
这启发我们将平方与一次项分开计算，设\(f_i\)表示已经买到了\(i\)种邮票，还要买期望\(f_i\)次才能买到\(n\)种，而\(g_i\)表示已买\(i\)个，还要买的次数平方的期望。
则容易写出状态转移方程：
\[\left\{ \begin{aligned} f_i&=\frac{i}{n}f_i+\frac{n-i}{n}f_{i+1} \\ g_i&=\frac{i}{n}(g_i+2f_i+1)+\frac{n-i}{i}(g_{i+1}+2f_{i+1}+1) \\ \end{aligned} \right. \]移项化简可以得到：
\[\left\{ \begin{aligned} f_i&=f_{i+1}+\frac{n}{n-i} \\ g_i&=\frac{i}{n}(g_i+2f_i+1)+\frac{n-i}{i}(g_{i+1}+2f_{i+1}+1) \\ \end{aligned} \right. \]#define N 5005005
double f[N],g[N];
int n;
int main(){
cin>>n;
for(int i=n-1;i>=0;--i){
f[i]=f[i+1]+1.0*n/(n-i);
g[i]=1.0*n/(n-i)+2.0*i/(n-i)*f[i]+2.0*f[i+1]+g[i+1];
}
printf("%.2f\n",(f[0]+g[0])/2.0);
}