Skip to content

Math Problems

算法竞赛（Competitive Programming）中的概率与期望题目虽然听起来很数学，但实际上它们往往通过 动态规划（DP） 或者 组合数学 的方式来解决。

这类题目主要考察两个核心点：状态转移的逻辑 和 数学性质的利用（特别是期望的线性性质）。

以下是概率题常见的“套路”归纳及经典例题解析。

一、 核心概念与工具

在深入套路之前，必须掌握这两个基础工具：

  1. 期望的线性性质 (Linearity of Expectation) 这是算法竞赛中最强大的工具。对于任意两个随机变量 X 和 Y（无论是否独立）：

E[X+Y]=E[X]+E[Y]

应用： 将一个复杂的总体期望拆解成无数个简单的“指示变量”的概率之和。

  1. 全概率/全期望公式 用于 DP 转移：

E[current]=∑P(next)×(E[next]+cost)

其中 cost 通常是 1（代表走了一步）。

二、 常见套路总结

套路 1：概率 DP vs. 期望 DP

这是最基础也是最常见的一类。

  • 概率 DP (Probability DP):
  • 定义： 通常定义 dp[i] 为“到达状态 i 的概率”。
  • 方向： 通常是 正向推导（从初始状态推向结束状态）。
  • 公式： dp[next]+=dp[current]×P(current→next)
  • 期望 DP (Expectation DP):
  • 定义： 通常定义 dp[i] 为“从状态 i 到达目标状态的 期望代价/步数”。
  • 方向： 通常是 逆向推导（因为目标状态的期望代价通常为 0，起点的期望代价是答案）。
  • 公式： dp[i]=∑P(i→j)×(dp[j]+w(i,j))。如果是求步数， w(i,j)=1。

套路 2：利用“指示变量”拆解问题

当题目问“某种复杂结构出现的期望次数/总和”时，千万不要试图去遍历所有可能的状态空间。

  • 方法：
  • 定义 Xi 为第 i 个局部结构（如一个位置、一条边）是否满足条件的指示变量（满足为 1，不满足为 0）。
  • 计算每个 Xi 发生的概率 P(Xi)。
  • 利用 E[Xi]=1×P(Xi)+0×(1−P(Xi))=P(Xi)。
  • 总期望 E=∑P(Xi)。

套路 3：带环图与高斯消元

如果状态转移图中存在 环（即你可以从 A 走到 B，又可能从 B 走回 A），传统的 DP 无法确定计算顺序（有后效性）。

  • 方法：
  • 列出每个状态的期望方程：Ei=∑Pi→jEj+1。
  • 这会形成一个包含 N 个未知数 N 个方程的线性方程组。
  • 使用 高斯消元法 (Gaussian Elimination) 求解。时间复杂度通常是 O(N3)。

套路 4：模意义下的概率 (Modular Arithmetic)

现代比赛中，很多题目不要求输出浮点数，而是要求输出“答案对 109+7 取模”。

  • 核心： 分数 a/b(modP) 等价于 a×b−1(modP)。
  • 工具： 需要使用费马小定理求 乘法逆元。
  • 注意： 所有的加减乘除都要在模意义下进行，逻辑与浮点数完全一致。

三、 经典例题解析

例题 1：经典期望 DP（逆向推导）

题目描述： 你在玩一个游戏，当前在格子 0，目标是格子 N。每次投掷一枚 6 面骰子，投出点数 k，你就向前走 k 步。如果越过了 N（即位置 >N），则需要重新投掷直到刚好落在 N 或小于 N 的位置。如果在某些特定格子（飞行通道），你会直接飞到另一个指定格子。求到达 N 的期望投掷次数。

解析：

  1. 状态定义： dp[i] 表示从格子 i 到达目标 N 的期望步数。

  2. 边界条件： dp[N]=0（已经在目标，不需要再投）。

  3. 转移方程： 从 i 出发，有 1/6 的概率走到 i+1,i+2,...,i+6。

dp[i]=1+k=1∑661×dp[i+k]

注意：如果 i+k>N，这部分概率通常意味着“原地不动”或者“重新投掷”，具体看题目定义。如果题目说 >N 无效需重投，则方程会变形成依赖自身，需要移项求解。

  1. 特殊处理： 如果 i 是飞行通道入口，飞到 j，则 dp[i]=dp[j]。

  2. 实现： 从 N−1 倒序循环到 0 即可。

例题 2：线性性质（Bernoulli 试验扩展）

题目描述： 抛 N 次硬币，每次正面朝上的概率是 p。求“连续出现两次正面”这个模式出现的期望次数。 例如：H H H 算作 2 次（位置 1-2 和 位置 2-3）。

解析： 不要尝试去 DP 整个序列的状态。

  1. 分解： 考虑第 i 次投掷和第 i+1 次投掷这一对组合 (i,i+1)。
  2. 概率： 这两个位置同时为正面的概率是 p×p=p2。
  3. 指示变量： 设 Xi 为“位置 i 和 i+1 是 HH”的指示变量。E[Xi]=p2。
  4. 求和： 一共有 N−1 对相邻位置（从 1 到 N−1）。
  5. 答案： Total_E=∑i=1N−1E[Xi]=(N−1)×p2。

例题 3：Coupon Collector Problem（赠券收集者问题）

题目描述： 此时盒子里有 N 种不同的卡片。每次购买你有 1/N 的概率买到任意一种（概率均等）。问收集齐所有 N 种卡片，期望需要购买多少次？

解析： 这是一个非常经典的几何分布应用。

  1. 假设你现在已经收集了 k 种卡片。

  2. 下一次买到“新卡片”的概率是 Pnew=NN−k。

  3. 买到“旧卡片”的概率是 Pold=Nk。

  4. 这是一个几何分布：获得一次成功（新卡片）所需的期望步数是 1/Pnew。 即：Ek=N−kN。

  5. 总期望是收集第 1 张、第 2 张...到第 N 张的期望之和：

Answer=k=0∑N−1N−kN=NN+N−1N+⋯+1N=Ni=1∑Ni1

即 N×(调和级数)。

四、 快速判断策略

当你看到一道概率题时，按以下流程思考：

  1. 数据范围：
  2. N≤20：考虑 状压 DP (State Compression DP)。
  3. N≤1000 且有后效性/环：考虑 高斯消元。
  4. N≤105 或更大：肯定不是高斯消元，必须找 递推公式 或者利用 线性性质 直接推导数学公式。
  5. 输出要求：
  6. 输出小数：注意精度，通常用 double 或 long double。
  7. 输出模数：准备好逆元模板，全程整数运算。

五、 我可以为你做的下一步

概率题非常依赖练习。如果你想针对某个具体的知识点深入，我可以：

  1. 提供一段“高斯消元求期望”的 C++ 模板代码。
  2. 为你讲解“绿豆蛙的归宿”这类经典的 DAG 期望 DP 题目。
  3. 解释什么是“期望的线性性质”在图论（如随机游走）中的高级应用。

你想先了解哪一部分？

树上期望dp的套路

树上期望 DP 是算法竞赛中“概率/期望 DP”的一个重要分支。相比于普通图的期望 DP（通常需要高斯消元），树的结构特性（无环、层次分明）使得我们可以用 O(N) 的时间复杂度解决问题。

树上期望 DP 主要处理两类问题：

  1. 单向流动：子节点只依赖父节点，或父节点只依赖子节点（简单的树形 DP）。
  2. 双向依赖（随机游走）：当前节点的期望值同时依赖于 父节点 和 子节点（这是难点）。

以下是树上期望 DP 的核心套路和经典模型。

套路一：单向依赖（基础树形 DP）

这类题目通常有一个明确的“终点”或“方向”，比如从根走到叶子，或者从叶子走到根。

模型：

  • 自下而上（Subtree 汇聚）： dp[u] 表示 u 子树内的某种期望。
  • 转移：dp[u]=∑(dp[v]+w)×P(u→v)。
  • 自上而下（父节点传递）： dp[u] 表示从根或其他地方到达 u 的概率/期望。
  • 转移：dp[u]=dp[fa]×P(fa→u)。

经典例题： [Luogu P4316] 绿豆蛙的归宿

  • 题意： 给定一个 DAG（虽然不是树，但思想一致），从起点走到终点，每一步等概率选择出边，求路径期望总长度。

  • 解法： 逆推。设 dp[u] 为从 u 到终点的期望长度。

dp[u]=v∈next(u)∑degout[u]dp[v]+w(u,v)

终点 dp[T]=0，起点 dp[S] 即为答案。

套路二：双向依赖与“待定系数法”（核心难点）

这是树上随机游走最经典的套路。 场景： 在树上随机游走，从 u 走到相邻节点（父或子）的概率均等（或指定）。因为 u 的期望依赖 fa，fa 的期望又依赖 u，形成了互相依赖，看似需要高斯消元，但树上可以优化。

核心推导（Equation Transformation）

假设 E[u] 表示从 u 出发到达目标的期望步数/代价。 方程通常长这样：

E[u]=Pfa×E[fa]+v∈children∑(Pv×E[v])+Cost

由于 E[u] 和 E[fa] 互为变量，我们无法直接 DP。 解决策略： 既然是树，我们不妨假设 E[u] 和 E[fa] 存在线性关系：

E[u]=ku×E[fa]+bu

其中 ku 和 bu 是只与 u 的子树有关的系数。

步骤：

  1. 推导系数： 将 E[v]=kvE[u]+bv 代入 E[u] 的原始方程中。
  2. 整理方程： 将方程整理成 E[u]=(…)E[fa]+(…) 的形式。
  3. DFS 1（自底向上）： 计算出所有节点的 ku 和 bu。
  4. 叶子节点的 k,b 通常是已知的（边界条件）。
  5. DFS 2（自顶向下）： 利用 E[u]=kuE[fa]+bu 和已知的 E[root] 计算所有 E[u]。

经典例题：[HNOI2013] 游走 (Walk)

题意： 给定一个 N 个点的树，从点 1 开始随机游走，每次等概率走到相邻节点，直到走到点 N 结束。求每条边被经过的期望次数。

解析：

  1. 转化： 边 (u,v) 的期望经过次数 = E[经过节点 u 的次数]×P(u→v)+E[经过节点 v 的次数]×P(v→u)。核心变成了求每个节点被经过的期望次数 f[u]。

  2. 列方程： 对于 u (非终点 N)：

f[u]=v∈adj(u)∑deg[v]f[v]

特别地，对于起点，初始有 1 次：f[1]=∑⋯+1。

  1. 待定系数： 设 f[u]=ku×f[fa]+bu。 将子节点的 f[v]=kvf[u]+bv 代入原方程，整理得到 ku,bu 的递推式。

  2. 求解：

  3. 终点 f[N]=0（到了就停，不产生对别人的贡献，或者理解为吸收态）。

  4. 两遍 DFS 即可解出所有 f[u]。

套路三：贡献法（Linearity of Expectation）

有些题目问的是“期望深度”、“期望大小”的总和，直接算 DP 状态很复杂。 技巧： 利用期望的线性性质，计算每个节点/每条边对答案产生贡献的概率。

公式：

E[Total Value]=∑E[Value of component i]=∑(Vali×P(Component i exists/is chosen))

经典例题： 随机删边/点问题 题意： 假如有一棵树，每个点有 1/2 概率被染黑。求黑点连通块个数的期望。 解析： 连通块个数不好数。利用欧拉公式变形（在树上）：

连通块数=点数−边数

E[连通块数]=E[黑点数]−E[两端都是黑点的边数]

  • E[黑点数]=∑1×0.5=N/2。
  • E[黑边]=∑(u,v)∈EdgesP(u,v 都是黑)=(N−1)×0.25。 直接相减即可，完全不需要复杂的 DP。

题目：

套路四：树上换根 DP (Re-rooting)

如果题目问：“对于每一个节点 i，如果以 i 为出发点/根，求期望...”，这就是换根 DP。

步骤：

  1. 指定 1 为根： 先做一次普通的树形 DP（自底向上），求出 dp[1] 以及所有子树的贡献。
  2. 二次扫描（自顶向下）： 考虑父节点对子节点的贡献。
  3. 当我们从 u 换根到子节点 v 时，v 的答案由两部分组成：
    1. v 原本的子树贡献（第一遍 DFS 已知）。
    2. u 除去 v 这棵子树后，剩下的部分对 v 的贡献。

总结与代码模板思路

遇到树上期望题，按以下流程思考：

  1. 是计数转化吗？ 能否用 E=∑P 拆解成简单的点/边贡献？（套路三）
  2. 有明确终点吗？
  3. 有：直接推导 DP 方程。
  4. 涉及“随机游走”回头的：使用 待定系数法 (dp[u]=k⋅dp[fa]+b)。（套路二）
  5. 全源问题？ 需要求所有点的答案 -> 换根 DP。（套路四）

一、基础概率题

  1. 正态收益率叠加 已知某只股票日收益率 \(R_i \sim N(\mu, \sigma^2)\)，且独立同分布。 1）求连续 \(n\) 天总收益率 \(\sum_{i=1}^n R_i\) 的分布； 2）问：如果看“年化收益率”，如何近似写出其分布？

任意有限个相互独立的正态随机变量的线性组合仍然服从正态分布；

  1. 两个骰子点数和的分布 同时掷两个公平的六面骰子，设随机变量 \(X\) 为两骰点数之和。 1）写出 \(P(X = k)\) 的表达式（\(k=2,\dots,12\)）； 2）求 \(P(X \ge 10)\)。
  2. 扑克牌抽牌不放回 一副 52 张标准扑克牌（不区分花色，只区分点数）。从中随机抽 5 张： 1）抽到“恰好 2 张 A”的概率是多少？ 2）抽到“至少 1 张 A”的概率是多少？
  3. 球盒模型（简单超几何） 有一个箱子，里面有 5 个红球、7 个蓝球、8 个白球。 不放回地随机抽出 3 个球： 1）抽到 3 个颜色都不同的概率； 2）抽到至少 2 个红球的概率。
  4. 订单成功率问题 某支付系统中，单笔订单成功的概率为 \(p=0.97\)，不同订单独立。 1）一天内有 100 笔订单，至少有 1 笔失败的概率？ 2）近似情况下，如何用泊松分布近似计算“失败订单数 ≥ 2” 的概率？
  5. 二项分布简单题 某广告点击率 \(p=0.02\)，独立展示 1000 次。设 \(X\) 为点击次数。 1）写出 \(P(X=k)\) 的表达式； 2）用合适的近似方法估计 \(P(X \ge 30)\)（提示：可以考虑正态或泊松近似）。
  6. 独立同分布求和的方差 已知 \(X_1, \dots, X_n\) 独立同分布，\(\mathbb{E}[X_i]=\mu\)，\(\mathrm{Var}(X_i)=\sigma^2\)。 1）求 \(S_n = \sum_{i=1}^n X_i\) 的期望和方差； 2）求 \(\bar{X} = S_n / n\) 的期望和方差。

二、条件概率 / 贝叶斯题

  1. 异常检测（医疗检测同型题） 某系统中，有 1% 的订单是异常。检测系统对异常订单检测为“异常”的概率为 99%（召回率），对正常订单误报为“异常”的概率为 1%。 问：某订单被检测为“异常”的情况下，它真实是异常订单的概率是多少？
  2. 垃圾邮件过滤 设邮件中 5% 是垃圾邮件（Spam），95% 是正常邮件（Ham）。 过滤器对垃圾邮件识别为垃圾的概率为 98%，对正常邮件误判为垃圾的概率为 2%。 现观察到一封邮件被标记为垃圾邮件，问它实际上是垃圾邮件的概率？

  3. 两个盒子问题（经典） 有两个盒子：

  4. 盒子 A 里有 2 个红球、1 个蓝球；

  5. 盒子 B 里有 1 个红球、2 个蓝球。 随机等概率选一个盒子，然后从盒子中随机取一个球，发现是红球。 问：被选中的盒子是 A 的后验概率是多少？

  6. 报警系统 某仓库有 0.5% 的概率在某天发生入侵。报警系统在有入侵时报警概率为 99%，在无入侵时误报概率为 0.5%。 某天报警器响了，求当天真的发生入侵的概率。

  7. 疾病检测多次测量 某疾病患病率为 0.1%。检测方法对患病者阳性率为 99%，对健康者误检阳性率为 1%。 现对同一个人独立检测 2 次，结果都是阳性。问此人患病的后验概率（假设两次测试独立）。
  8. 异常多层筛查 某电商每天 10 万订单，历史上 1% 有欺诈风险。先用一个粗筛系统，召回率 95%，误报率 5%；然后对被粗筛标记为“可疑”的订单再用精细模型复检，复检的召回率为 99%，误报率为 1%。 问：通过两级筛查最终落在“高危名单”的订单中，真实欺诈订单的大致比例（可以给表达式即可）。

  9. 多类别贝叶斯分类 有三类客户：

  10. 高价值客户占 10%，会购买某产品的概率为 80%；

  11. 中价值客户占 30%，购买概率 40%；
  12. 低价值客户占 60%，购买概率 10%。 现在观察到一个随机客户完成了购买，问他是高价值客户的后验概率是多少？

三、期望 & 方差题

  1. 抛硬币直到出现第一个正面（几何分布） 硬币正面概率为 \(p\)，反面为 \(1-p\)。不断抛掷，直到首次出现正面为止。 1）设随机变量 \(N\) 表示所需次数，求 \(\mathbb{E}[N]\)； 2）求 \(\mathrm{Var}(N)\)。
  2. 骰子点数的期望和方差 掷一个公平六面骰子，点数为 \(1,\dots,6\)。 1）求点数的期望 \(\mathbb{E}[X]\)； 2）求方差 \(\mathrm{Var}(X)\)。
  3. 直到出现两个正面 公平硬币（正反均为 0.5），不断抛掷，直到“累计出现两个正面”为止。 1）设 \(N\) 为总抛掷次数，求 \(\mathbb{E}[N]\)； 2）给出计算思路（可以用负二项分布）。

  4. 排队服务时间（和的期望、方差） 客户到达某柜台后，需要完成两道独立手续：

  5. 第一道办理时间 \(X\)，\(\mathbb{E}[X]=2\) 分钟，\(\mathrm{Var}(X)=1\)；

  6. 第二道办理时间 \(Y\)，\(\mathbb{E}[Y]=3\) 分钟，\(\mathrm{Var}(Y)=4\)。 假设 \(X,Y\) 独立。 1）总时间 \(T=X+Y\) 的期望和方差是多少？ 2）如果有 10 个客户排队，每人总时间独立同分布为 \(T\)，求所有人办完的总时间的期望和方差。

  7. 随机游走一步的期望 一维随机游走：当前位置为 0，每一步以概率 \(p\) 向右走 1，以概率 \(1-p\) 向左走 1。 1）走一步后位置 \(X_1\) 的期望与方差是多少？ 2）走 \(n\) 步后位置 \(S_n = \sum_{i=1}^n X_i\) 的期望和方差？

  8. 抽奖期望收益 某抽奖活动规则：

  9. 以 0.9 的概率什么都得不到；

  10. 以 0.08 的概率获得 50 元；

  11. 以 0.02 的概率获得 500 元。 参加一次抽奖需要支付 10 元。 问：参加一次抽奖的期望净收益是多少？长期玩这游戏是赚还是亏？

  12. 优惠券收集（简化版） 某活动有 3 种不同的卡牌，每次随机获得一种，概率均等且独立。 1）从零开始收集，直到三种都集齐为止，所需抽取次数的期望？ 2）给出通用思路（推广到 \(n\) 种卡牌的情形）。

  13. 随机变量函数的期望 掷一次公平骰子，点数为 \(X\)。定义收益为
\[ Y = \begin{cases} 0, & X \le 3 \\ X^2, & X > 3 \end{cases} \]

求收益的期望 \(\mathbb{E}[Y]\) 和方差 \(\mathrm{Var}(Y)\)。

四、简单脑筋急转弯 / 思维题（灯 / 水壶 / 天平）

  1. 100 盏灯问题（经典变体） 有 100 盏灯，编号 1 到 100，起初全部关闭。 有 100 个人依次操作，第 \(k\) 个人会“切换”所有编号为 \(k\) 的倍数的灯（开→关，关→开）。 问：所有人操作完后，最后有几盏灯是亮着的？它们的编号是什么？（你可以先从小规模，如 10 盏灯，开始观察模式。）
  2. 一般化灯问题 将上题推广：有 \(N\) 盏灯、\(N\) 个人。写出对任意 \(N\) 时，亮灯的编号特征（可描述为一种数学性质）。
  3. 三水壶问题 有容量分别为 8 升、5 升、3 升的三个水壶，其中 8 升壶装满水，其他为空。没有量杯。 你可以在壶之间任意倒水，但不能估量中间刻度。 问：是否有办法得到恰好 4 升水？如果有，给出操作步骤；如果没有，说明理由。
  4. 两边天平找次品（称重） 有 12 枚外观完全相同的硬币，其中有 1 枚是假币，重量未知，只知道它比真币要重或轻，但不知道是重还是轻。 使用一个两边天平（只能比较左右哪边重），问： 1）在最优策略下，最多用 3 次称重是否能一定找出假币并判断其轻重？ 2）如果可以，请给出大致策略思路。
  5. 一堆求最重硬币 有 9 个外观一样的砝码，其中 1 个比其他的重，其余 8 个重量相同。 用两边天平，最少需要几次称重就可以保证找出最重的那个？给出策略。
  6. 水壶装水时间问题（算法味道） 有一台饮水机，出水速度恒定。你有一个容量为 5L 的壶和一个容量为 3L 的壶，都没有刻度。 现在想量出 4L 的水装入 5L 壶，允许你多次装满/倒掉水。问题： 1）是否可行？ 2）如果可行，写出一个“操作序列算法”（用步骤表示状态变换）。
  7. 运算符插入（思维+穷举） 给定数字 1,2,3,4，可以在它们之间插入 “+”、“-”、“×”、“÷”、括号，使得表达式结果等于 24。 问：能否构造出一个合法表达式？如果可以，给出一个例子；如果不可以，说明理由。 （这个题本身不难，主要考察你构造 / 搜索思路，可以扩展为用程序搜索。）
  8. 一维线段切割（几何期望思维） 在长度为 1 的线段上随机独立选取 2 个点，将线段分成 3 段。 问：这 3 段能构成三角形的概率是多少？ （提示：可以画二维平面区域，转化为几何概率。）