C++ 算法技巧 — 概率 (Probability)

章节概述

概率类题目通常涉及期望、数学推导或动态规划求解概率值。
核心数学工具是期望的线性性和条件概率。

核心原理

1. 期望的线性性

$E(X+Y)=E(X)+E(Y)$

不需要 X 和 Y 独立。这意味着可以将复杂期望分解为各组成部分期望之和。

2. 期望 DP 的两种推进方向

方向	描述	示例
正向递推	从初始状态推到终态	OSU! 递推 e1, e2
逆向递推	从终态反推到初始状态	搞笑世界杯 dp[i][j]

3. 关键数学公式

• 连续成功得分的递推: $(x+1{)}^3=x^3+3x^2+3x+1$
• 相邻题做对概率: $\frac{\min (a_i,a_{i+1})}{a_i\cdot a_{i+1}}$
• 条件转移: $dp[i][j]=p_1\cdot dp[i-1][j]+p_2\cdot dp[i][j-1]$

关键数据结构

• A_容器_Container — DP 表格存储

---

P1297 [国家集训队] 单选错位

题目: n 道单选题串行填涂，求做对题目的期望数量。

#include <cstdio>
#include <algorithm>
using namespace std;
int a[10000005];
 
int main() {
    int n, A, B, C;
    scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
    for (int i = 2; i <= n; i++)
        a[i] = ((long long)a[i - 1] * A + B) % 100000001;
    for (int i = 1; i <= n; i++)
        a[i] = a[i] % C + 1;
    double ans = 0;
    for (int i = 1; i < n; i++)
        ans += min(a[i], a[i + 1]) / (double)(a[i] * a[i + 1]);
    ans += min(a[n], a[1]) / (double)(a[n] * a[1]);
    printf("%.3f\n", ans);
    return 0;
}

---

P1654 OSU!

题目: n 次操作，第 i 次成功概率 p_i。连续 x 次成功得 x^3 分，失败重置。求期望总得分。

思路: 利用 $(x+1{)}^3=x^3+3x^2+3x+1$，维护一次期望 e1 和二次期望 e2。

#include <cstdio>
using namespace std;
 
int main() {
    int n;
    scanf("%d", &n);
    double ans = 0, e1 = 0, e2 = 0;
    for (int i = 0; i < n; i++) {
        double p;
        scanf("%lf", &p);
        ans += p * (3 * e2 + 3 * e1 + 1);
        e2 = p * (e2 + 2 * e1 + 1);
        e1 = p * (e1 + 1);
    }
    printf("%.1f\n", ans);
    return 0;
}

---

P2719 搞笑世界杯

题目: 2n 张票(n 张 A, n 张 B)，卖到只剩一种球迷时”搞笑”。求期望售出票数。
dp[i][j] = 还剩 i 张 A 和 j 张 B 时的期望。

#include <cstdio>
using namespace std;
double dp[1255][1255];
 
int main() {
    int n;
    scanf("%d", &n);
    n /= 2;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = i / (double)(i + j) * (dp[i - 1][j] + 1)
                     + j / (double)(i + j) * (dp[i][j - 1] + 1);
    printf("%.4f\n", dp[n][n]);
    return 0;
}

推荐练习题（洛谷）

• P1000 超级玛丽游戏
• P1001 A+B Problem

---

相关技巧

---

• 递推递归: 期望 DP 的递推公式
• 搜索: DFS 枚举所有概率路径
• 暴力枚举: 枚举所有可能情况计算概率

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |