6月份做的这道题，今天再看，发现有些地方的理解是错的，修改了一下发了上来。
Des
有 (n) 种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是 (n) 种邮票中的哪一种是等概率的，概率均为 (1/n)。但是由于凡凡也很喜欢邮票，所以皮皮购买第 (k) 次邮票需要支付 (k) 元钱。
现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。
( exttt{Data Range:})
(Nle 10^4)
Sol
设 (f(k)) 表示买到 (k) 张不同邮票的期望次数，(f(k)=sum p_jn_j)，则费用 (g(k)) 为
[sum p_jfrac {(1+n_j)(n_j)}{2}=frac{sum p_jn_j+sum p_jn_j^2}{2}=frac{f(k^2)+f(k)}{2}
]
所以需要维护 (f(k^2)) 和 (f(k))。
设 (f(k-1)=sum q_jm_j)，(f(k)=sum h_qs_q)，则
[egin{align*}
f(k)&=frac{n-k+1}nsum q_j(m_j+1)+frac{k-1}n(sum h_q(s_q+1))\
&=frac{n-k+1}n(f(k-1)+1)+frac{k-1}n(f(k)+1)\
&=f(k-1)+frac{n}{n-k+1},
end{align*}
]
同理，
[egin{align*}
f(k^2)&=frac{n-k+1}{n}sum q_j(m_j+1)^2+frac{k-1}{n}sum h_q(s_q+1)^2\
&=frac{n-k+1}{n}(f(k-1)^2+2f(k-1)+1)+frac{k-1}{n}(f(k^2)+2f(k)+1)\
&=f((k-1)^2)+2f(k-1)+1+frac{k-1}{n-k+1}(2f(k)+1).
end{align*}
]
这样就比较轻松的解决了这个问题，关键在于不能将期望 (E(k)) 看做一个整体考虑，而应该写成定义式再做运算。另外就是期望的平方不一定等于平方的期望。
My code
const int N = 1e4 + 5;
int n;
double f[N], f2[N];
int main() {
#ifndef HRJ
ios::sync_with_stdio(false); cin.tie(0);
#endif
cin >> n;
for(int i = 1; i <= n; i++) {
f[i] = f[i - 1] + double(n) / (n - i + 1);
f2[i] = f2[i - 1] + 2 * f[i - 1] + 1 + double(i - 1) / (n - i + 1) * (2 * f[i] + 1);
}
cout << fixed << setprecision(2) << (f[n] + f2[n]) / 2;
return 0;
}