题解 | #超多面骰子#

题目链接

超多面骰子

题目描述

给定一个有 $N$ 个面的均匀骰子，求期望需要投掷多少次，才能使每一面都至少出现一次。

输入:

第一行一个整数 $T$ ，表示测试用例数量。
接下来 $T$ 行，每行一个整数 $N$ ，表示骰子的面数。

输出:

对于每个测试用例，输出一行一个实数，表示期望投掷次数。

解题思路

这是一个经典的概率期望问题，通常被称为赠券收集问题 (Coupon Collector's Problem)。

1. 定义状态和随机变量

设 $X$ 为集齐所有 $N$ 个面所需的总投掷次数。我们要求的是 $E[X]$ 。
我们可以将整个过程分解为 $N$ 个阶段：
- 第 0 阶段：已经集齐 0 个面，目标是集齐第 1 个面。
- 第 1 阶段：已经集齐 1 个面，目标是集齐第 2 个面。
- ...
- 第 $i$ 阶段：已经集齐 $i$ 个面，目标是集齐第 $i+1$ 个面。
- ...
- 第 $N-1$ 阶段：已经集齐 $N-1$ 个面，目标是集齐最后一个面。
设 $X_i$ 为在已经集齐 $i$ 个不同的面之后，为了集齐第 $i+1$ 个新面所需要投掷的次数。这是一个随机变量。
那么，总投掷次数 $X = X_0 + X_1 + \dots + X_{N-1}$ 。

2. 利用期望的线性性质

根据期望的线性性质， $E[X] = E[\sum_{i=0}^{N-1} X_i] = \sum_{i=0}^{N-1} E[X_i]$ 。
现在，问题转化为求每个阶段的期望投掷次数 $E[X_i]$ 。

3. 计算每个阶段的期望

考虑第 $i$ 阶段：我们已经集齐了 $i$ 个不同的面。
每次投掷，有 $N$ 个等可能的结果。
- 投掷到一个新的面（我们还没见过的面）的概率是 $p_i = \frac{N-i}{N}$ 。
- 投掷到一个旧的面（我们已经见过的面）的概率是 $1 - p_i = \frac{i}{N}$ 。
$X_i$ 遵循几何分布。几何分布描述的是：在每次成功的概率为 $p$ 的伯努利试验中，为了取得第一次成功所需要的试验次数。其期望值为 $1/p$ 。
因此，在第 $i$ 阶段，为了投出那 $N-i$ 个新面中的任意一个，期望的投掷次数为： $E[X_i] = \frac{1}{p_i} = \frac{1}{(N-i)/N} = \frac{N}{N-i}$ 。

4. 汇总计算

将所有阶段的期望相加，得到总期望： $E[X] = \sum_{i=0}^{N-1} E[X_i] = \sum_{i=0}^{N-1} \frac{N}{N-i}$
展开这个和式： $E[X] = \frac{N}{N-0} + \frac{N}{N-1} + \dots + \frac{N}{N-(N-1)} = \frac{N}{N} + \frac{N}{N-1} + \dots + \frac{N}{1}$
提出公因子 $N$ ： $E[X] = N \cdot (\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{N}) = N \cdot H_N$ 其中 $H_N = \sum_{k=1}^{N} \frac{1}{k}$ 是第 $N$ 个调和数。

5. 算法实现

由于 $N$ 的值可能很大，我们可以预先计算并存储调和数的前缀和。
创建一个数组 H，H[i] 存储第 $i$ 个调和数的值。
循环 $T$ 次，对于每个输入的 $N$ ，直接查询 H[N] 并乘以 $N$ 即可得到答案。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

const int MAXN = 1000001;
vector<double> h_sum(MAXN);

void precompute_harmonic() {
    h_sum[0] = 0.0;
    for (int i = 1; i < MAXN; ++i) {
        h_sum[i] = h_sum[i - 1] + 1.0 / i;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    precompute_harmonic();

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        double expected_value = n * h_sum[n];
        cout << fixed << setprecision(10) << expected_value << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MAXN = 1000001;
    static double[] hSum = new double[MAXN];

    public static void precomputeHarmonic() {
        hSum[0] = 0.0;
        for (int i = 1; i < MAXN; i++) {
            hSum[i] = hSum[i - 1] + 1.0 / i;
        }
    }

    public static void main(String[] args) {
        precomputeHarmonic();

        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            double expectedValue = n * hSum[n];
            System.out.printf("%.10f\n", expectedValue);
        }
    }
}

MAXN = 1000001
h_sum = [0.0] * MAXN

def precompute_harmonic():
    for i in range(1, MAXN):
        h_sum[i] = h_sum[i - 1] + 1.0 / i

def main():
    precompute_harmonic()
    
    t = int(input())
    for _ in range(t):
        n = int(input())
        expected_value = n * h_sum[n]
        print(f"{expected_value:.10f}")

if __name__ == "__main__":
    main()

算法及复杂度

算法：数学期望 (赠券收集问题) + 前缀和预处理
时间复杂度：预处理调和数数组的时间复杂度为 $\mathcal{O}(\text{MAXN})$ 。之后，对于每个测试用例，查询是 $\mathcal{O}(1)$ 的。因此，总时间复杂度为 $\mathcal{O}(\text{MAXN} + T)$ 。
空间复杂度：需要一个数组来存储调和数的前缀和，空间复杂度为 $\mathcal{O}(\text{MAXN})$ 。