题解 | 超多面骰子 #

$[概率论(几何分布)]$

一个拥有 $n$ 个面的骰子，期望投掷多少次才能保证每一面都至少出现过一次？

设随机变量 $X$ 表示上述条件所需的投掷次数，求 $E(X)$

设：

$X_{0}$ 表示：现在已经有 $0$ 个面了，还需要期望投掷 $X_{0}$ 次会有 $1$ 个面

$X_{1}$ 表示：现在已经有 $1$ 个面了，还需要期望投掷 $X_{1}$ 次会有 $2$ 个面

$X_{2}$ 表示：现在已经有 $2$ 个面了，还需要期望投掷 $X_{2}$ 次会有 $3$ 个面

...

$X_{n-1}$ 表示：现在已经有 $n-1$ 个面了，还需要期望投掷 $X_{n-1}$ 次会有 $n$ 个面

那么 $E(X)=E(X_{0}+X_{1}+X_{2}+...+X_{n-1})=E(X_{0})+E(X_{1})+E(X_{2})+...+E(X_{n-1})$

即转化为求 $E(X_{i})$ 了：

现在已经有 $2$ 个面了，还需要期望投掷 $X_{i}$ 次会有 $3$ 个面

那么直接投掷出还没有出现的面的概率为 $P=\frac{n-i}{n}$ ，投掷出已经出现过的面的概率为 $1-P=\frac{i}{n}$

几何分布：几何分布是离散型机率分布。描述第 $n$ 次伯努利试验成功的机率。详细的说，是： $n$ 次伯努利试验，前 $n -1$ 次皆失败，第 $n$ 次才成功的概率。

概率： $P(X=k)=(1-p)^{k-1}\times p$

期望： $\frac{1}{P}$

方差： $\frac{1-P}{P^{2}}$

所以 $E(X_{i})=\frac{1}{P}=\frac{n}{n-i}$

那么： $E(X)=E(X_{0})+E(X_{1})+E(X_{2})+...+E(X_{n-1})=\frac{n}{n-0}+\frac{n}{n-1}+\frac{n}{n-2}+...+\frac{n}{2}+\frac{n}{1}$

即 $E(X)=E(X_{0})+E(X_{1})+E(X_{2})+...+E(X_{n-1})=\frac{n}{n-0}+\frac{n}{n-1}+\frac{n}{n-2}+...+\frac{n}{2}+\frac{n}{1}$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


signed main(){
    HelloWorld;
    
    int n; cin >> n;
    double ans = 0;
    for(int i = 1; i <= n; i ++){
        ans += 1.0 / (n - i + 1);
    }
    ans = ans * 1.0 * n;
    cout << fixed << setprecision(9) << ans << endl;
    return 0;
}