InoueMoby's Blog

前言

高中数学讲过期望： $E[X] = \sum x_i \cdot P(X=x_i)$ 。但竞赛中的期望题很少直接用定义算——而是反复使用期望的线性性： $E[X+Y] = E[X] + E[Y]$ 。这个等式在 $X, Y$ 不独立时也成立！这意味着我们可以把复杂问题拆成若干简单随机变量之和，分别求期望再相加。

问题的本质

期望的线性性

为什么 $E[X+Y] = E[X] + E[Y]$ 不需要独立？因为：

$E[X+Y] = \sum_{x,y} (x+y) \cdot P(X=x, Y=y) = \sum_x x \sum_y P(X=x, Y=y) + \sum_y y \sum_x P(X=x, Y=y)$

右边就是 $E[X] + E[Y]$ 。无论 $X, Y$ 是否独立，这个等式都成立。

追问：那 $E[XY] = E[X] \cdot E[Y]$ 呢？这需要独立！展开后交叉项无法分离。

概率 DP

很多期望题的递推关系形如：

$dp[i] = c_i + \sum_{j} p_{ij} \cdot dp[j]$

其中 $dp[i]$ 表示从状态 $i$ 出发的期望花费。这实际上是解一个线性方程组。当状态转移形成 DAG 时，可以按拓扑序 DP；有环时需要高斯消元。

优惠券收集者问题

$N$ 种卡片，每次随机抽到一种。集齐全部 $N$ 种的期望次数？

设 $X_i$ = 从已有 $i-1$ 种到有 $i$ 种所需的抽卡次数。 $X_i$ 服从参数为 $(N-i+1)/N$ 的几何分布， $E[X_i] = N/(N-i+1)$ 。

$E[X] = \sum_{i=1}^{N} \frac{N}{N-i+1} = N \sum_{k=1}^{N} \frac{1}{k} = N \cdot H_N \approx N \ln N$

其中 $H_N$ 是第 $N$ 个调和数。

理论 + 代码

模板：独立随机变量的期望之积

当 $X_1, \ldots, X_N$ 独立时， $E[\prod X_i] = \prod E[X_i]$ 。这在”骰子乘积”类问题中直接使用。

// N 个骰子，第 i 个有面值 A[i][0..5]，求所有出面的乘积的期望 mod 10^9+7
// 因为每个骰子独立，E[product] = prod E[one die]
long long ans = 1;
for (int i = 0; i < N; i++) {
    long long sum = 0;
    for (int j = 0; j < 6; j++)
        sum = (sum + A[i][j]) % MOD;                   // ① 单个骰子的期望
    ans = ans * sum % MOD;                             // ② 独立→乘积
    ans = ans * power(6, MOD - 2, MOD) % MOD;         // ③ 除以 6（乘以逆元）
}

逐行解析：

① 第 $i$ 个骰子的期望 $= \sum A[i][j] / 6$ 。
② 独立随机变量的期望之积 = 期望的积。
③ 模意义下除法用逆元。

模板：优惠券收集者

double coupon_collector(int N) {
    double ans = 0;
    for (int k = 1; k <= N; k++)
        ans += 1.0 / k;                                // ① 调和级数
    return ans * N;                                     // ② 乘以 N
}

模板：期望逆序对

$N$ 个位置，第 $i$ 个位置的值在 $[L_i, R_i]$ 上均匀分布。求期望逆序对数。

由期望的线性性， $E[\text{inv}] = \sum_{i<j} P(a_i > a_j)$ 。每对独立计算。

例题

例题 1：M&A 023 — Dice Expectation（期望线性性）

题目：蓝骰子有面值 $B_1, \ldots, B_N$ ，红骰子有面值 $R_1, \ldots, R_N$ 。掷两个骰子，求面值之和的期望。

数据范围： $2 \le N \le 10^5$

—— AtCoder M&A 023

分析： $E[\text{sum}] = E[\text{blue}] + E[\text{red}]$ ，由期望的线性性。

输入样例：

3
1 2 3
10 20 30

输出：22.000000000000

验证： $E[\text{blue}] = (1+2+3)/3 = 2$ ， $E[\text{red}] = (10+20+30)/3 = 20$ 。 $E[\text{sum}] = 22$ 。✓

代码：

#include <cstdio>
int main() {
    int N;
    scanf("%d", &N);
    double sumB = 0, sumR = 0;
    for (int i = 0; i < N; i++) { int x; scanf("%d", &x); sumB += x; }
    for (int i = 0; i < N; i++) { int x; scanf("%d", &x); sumR += x; }
    printf("%.12f\n", sumB / N + sumR / N);            // ① 线性性
}

逐行解析：

① $E[X+Y] = E[X] + E[Y]$ ，蓝骰子和红骰子的期望分别计算。

例题 2：T90 052 — Dice Product（独立期望之积）

题目： $N$ 个 6 面骰子，第 $i$ 个骰子的第 $j$ 面为 $A_{i,j}$ 。求所有 $6^N$ 种出面的乘积之和对 $10^9+7$ 取模。

数据范围： $1 \le N \le 100$

—— AtCoder Typical 90 052

分析：乘积之和 = $6^N \cdot E[\prod R_i] = 6^N \cdot \prod E[R_i]$ （独立性）。每个 $E[R_i] = \sum_j A_{i,j}$ 。

代码：

#include <cstdio>
const long long MOD = 1000000007;

long long power(long long a, long long b) {
    long long res = 1;
    while (b > 0) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; }
    return res;
}

int main() {
    int N;
    scanf("%d", &N);
    long long ans = 1;
    long long inv6 = power(6, MOD - 2);                // ① 6 的逆元
    for (int i = 0; i < N; i++) {
        long long sum = 0;
        for (int j = 0; j < 6; j++) { int x; scanf("%d", &x); sum = (sum + x) % MOD; }
        ans = ans * sum % MOD;                         // ② E[product] = prod E[one]
        ans = ans * inv6 % MOD;                        // ③ 除以 6
    }
    printf("%lld\n", ans);
}

逐行解析：

① 预计算 $6^{-1} \pmod{10^9+7}$ 。
②③ 乘积的期望 = 期望的乘积。每个 $E[R_i] = \text{sum} / 6$ 。

验证：样例 1， $N=2$ 。骰子 1: {1,2,3,5,7,11}, 和=29。骰子 2: {4,6,8,9,10,12}, 和=49。 $E_1 = 29/6, E_2 = 49/6$ 。 $6^2 \times E_1 \times E_2 = 36 \times 29/6 \times 49/6 = 29 \times 49 / 36 \times 36 = 29 \times 49 = 1421$ 。✓

例题 3：M&A 026 — Coin Gacha（优惠券收集者）

题目： $N$ 种硬币，每次花 1 元等概率抽一种。集齐全部的期望花费。

数据范围： $2 \le N \le 10^6$

—— AtCoder M&A 026

分析：标准优惠券收集者。答案 $= N \cdot H_N = N \sum_{k=1}^{N} 1/k$ 。

代码：

#include <cstdio>
int main() {
    int N;
    scanf("%d", &N);
    double ans = 0;
    for (int k = 1; k <= N; k++)
        ans += 1.0 / k;                                // ① 调和级数
    printf("%.12f\n", ans * N);                         // ② 乘以 N
}

逐行解析：

① $H_N = \sum_{k=1}^{N} 1/k$ ，调和级数。
② $N \cdot H_N$ 。

验证： $N=5$ 。 $H_5 = 1 + 1/2 + 1/3 + 1/4 + 1/5 = 137/60 \approx 2.2833$ 。 $5 \times 137/60 = 685/60 \approx 11.4167$ 。✓

例题 4：T90 066 — Various Arrays（期望逆序对）

题目： $N$ 个位置，第 $i$ 个的值在 $[L_i, R_i]$ 上均匀随机。求期望逆序对数。

数据范围： $1 \le N \le 100$ ， $1 \le L_i \le R_i \le 100$

—— AtCoder Typical 90 066

分析：由期望的线性性， $E[\text{inv}] = \sum_{i<j} P(a_i > a_j)$ 。每对独立计算：

$P(a_i > a_j) = \frac{1}{(R_i-L_i+1)(R_j-L_j+1)} \sum_{x=L_i}^{R_i} \max(0, x - L_j)$

即 $a_j$ 的可能值中小于 $x$ 的个数之和。

代码：

#include <cstdio>
int L[109], R[109];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%d%d", &L[i], &R[i]);

    double ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {              // ① 每对 (i, j)
            double cnt = 0;
            for (int x = L[i]; x <= R[i]; x++) {
                // P(a_j < x) = max(0, x - L[j]) / (R[j]-L[j]+1)
                // 但 a_j < x 即 a_j <= x-1
                if (x > L[j]) {
                    cnt += min(x - 1, R[j]) - L[j] + 1; // ② a_j < x 的可能值数
                }
            }
            double pi = (double)(R[i] - L[i] + 1) * (R[j] - L[j] + 1);
            ans += cnt / pi;                            // ③ P(a_i > a_j)
        }
    }
    printf("%.12f\n", ans);
}

逐行解析：

① 枚举所有逆序对 $(i, j)$ ， $i < j$ 。
② 对于固定的 $a_i = x$ ， $a_j < x$ 的可能值数量。
③ $P(a_i > a_j)$ = 有利情况 / 总情况。

验证：样例 1， $N=2, [1,2],[1,2]$ 。 $P(a_1 > a_2) = P((2,1)) = 1/4 = 0.25$ 。✓

参考文献

基础练习 — アルゴリズムと数学演習問題集

实战练习 — 競プロ典型 90 問

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

期望与概率

掷骰子抽卡的数学——期望的线性性是解题利器

前言

问题的本质

期望的线性性

概率 DP

优惠券收集者问题

理论 + 代码

模板：独立随机变量的期望之积

模板：优惠券收集者

模板：期望逆序对

例题

例题 1：M&A 023 — Dice Expectation（期望线性性）

例题 2：T90 052 — Dice Product（独立期望之积）

例题 3：M&A 026 — Coin Gacha（优惠券收集者）

例题 4：T90 066 — Various Arrays（期望逆序对）

参考文献

系列索引

期望与概率