收集邮票 [概率]

失踪人口回归系列2333

当年学OI的时候还是在bzoj上做这道题，困扰了当时只会高中概率知识的我好长时间。

现在我学了概统了，可以吊锤这道题了！

设期望张数为(X)，则答案为(E(frac{X+X^2}{2})=frac{EX+EX^2}{2})，需要计算(EX)和(EX^2)。

考虑已经有k-1种不同邮票，要买到第k种，就是有(frac{k-1}{n})的概率失败(frac{n-k+1}{n})的概率成功，是一个几何分布，所以可知(X=X_1+X_2+…+X_n, X_k sim G(frac{n-k+1}{n}))。

对于几何分布(Xsim G(p))，有(EX=frac{1}{p}, var(X)=frac{1-p}{p^2})

所以，$$EX=E(sum_{i=1}^n X_i) = sum_{i=1}^n EX_i = nsum_{i=1}^n frac{1}{i}$$

[egin{align*} EX^2 & = E(sum X_i^2 + sum_{i eq j}X_i X_j) \ &= sum EX_i^2 + sum_{i eq j}E(X_i X_j)\ &= sum var(X_i)+(EX_i)^2 + sum_{i eq j}(EX_i)(E X_j)\ &= sum_{k=1}^n (frac{2n^2}{k^2}-frac{n}{k})+sum_{i eq j}frac{n^2}{ij} \ end{align*} ]

（由于(X_i, X_j, i eq j)独立，所以(E(X_iX_j)=(EX_i)(EX_j))

所以，(ans = n^2sum_{i=1}^n sum_{j=i}^n frac{1}{ij})，完成了！

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int n;
int main() {
    cin >> n;
    double ans = 0, t = 0;
    for(int i=1; i<=n; i++) {
        t += 1.0/i;
        ans += 1.0/i * t;
    }
    ans *= n*n;
    printf("%.2f", ans);
}