掌握概率论与动态规划：图论中的状态转移与贝叶斯推导

核心逻辑与数学原理

概率论是处理竞赛中不确定性决策与期望动态规划（DP）的数学基石。在 NOIP 级别考察中，概率论的边界通常严格限定在离散样本空间内。

1. 样本空间与条件概率

设 $\Omega$ 为离散有限样本空间，$A$ 和 $B$ 为其中的两个事件。

条件概率（Conditional Probability）：在事件 $B$ 已经发生的前提下，事件 $A$ 发生的概率，记作 $P(A \mid B)$：

$$P(A \mid B) = \frac{P(A \cap B)}{P(B)} \text{ (如果 } P(B) > 0 \text{)}$$

在算法竞赛中，条件概率常用于状态步进时的转移系数修正。

2. 全概率公式（Law of Total Probability）

设 $B_1, B_2, \dots, B_n$ 为样本空间 $\Omega$ 的一个划分（即各事件两两互斥，且 $\bigcup_{i=1}^n B_i = \Omega$，$P(B_i) > 0$）。则对任意事件 $A$，均有：

$$P(A) = \sum_{i=1}^n P(A \mid B_i) P(B_i)$$

竞赛图论边界：全概率公式在图论拓扑网络或 DP 状态机中，对应当前节点的状态概率是由其所有前驱节点转化而来的加权总和。

3. 贝叶斯公式（Bayes' Theorem）

基于条件概率与全概率公式，用于实现“执果索因”的反向概率推导：

$$P(B_j \mid A) = \frac{P(A \mid B_j) \times P(B_j)}{P(A)} = \frac{P(A \mid B_j) \times P(B_j)}{\sum_{i=1}^n P(A \mid B_i) P(B_i)}$$

在已知某种结果 $A$ 发生的条件下，贝叶斯公式能够精确计算出是由特定原因 $B_j$ 引起的后验概率。

状态设计与算法推导

在常见的概率动态规划（Probability DP）中，我们通常需要维护某种特定状态发生的绝对概率。

拓扑图上的概率状态设计

设 $f[u]$ 表示流程运行到图中有向节点 $u$ 的概率。假设节点 $u$ 有若干个入边来自前驱集合 $pre(u)$。对于每个前驱节点 $v \in pre(u)$，从 $v$ 走到 $u$ 的转移概率（分支系数）为 $w(v, u)$，且满足 $\sum_{k \in post(v)} w(v, k) = 1$（即出边概率归一化）。

根据全概率公式，节点 $u$ 的状态转移方程为：

$$f[u] = \sum_{v \in pre(u)} f[v] \times w(v, u)$$

执行序判定：

若图结构为有向无环图（DAG）：直接利用拓扑排序严格控制计算顺序，在 $O(N + M)$ 线性时间内一向扫描推导填表。
边界条件：起点 $S$ 初始化状态为 $f[S] = 1$，其余所有节点初始概率 $f[u] = 0$。

C++ 标准源码

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

// 边的结构体定义
struct Edge {
    int to;
    double prob; // 转移条件概率 P(to | from)
};

const int MAXN = 100000;
std::vector<Edge> graph[MAXN + 5];
int in_degree[MAXN + 5];
double f[MAXN + 5]; // 状态数组：存储到达每个节点的绝对概率

// 拓扑排序跑 DAG 概率动态规划
void compute_probability_dp(int n, int start_node) {
    std::queue<int> q;

    // 初始化边界：起点概率为 1，其余默认为 0
    f[start_node] = 1.0;

    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (const auto &edge : graph[u]) {
            int v = edge.to;
            // 核心转移：全概率公式代数累加
            f[v] += f[u] * edge.prob; 

            if (--in_degree[v] == 0) {
                q.push(v);
            }
        }
    }
}

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

    int n, m, start_node;
    if (std::cin >> n >> m >> start_node) {
        for (int i = 0; i < m; ++i) {
            int u, v;
            double p;
            std::cin >> u >> v >> p;
            graph[u].push_back({v, p});
            in_degree[v]++;
        }

        compute_probability_dp(n, start_node);

        // 输出目标终点的概率
        for (int i = 1; i <= n; ++i) {
            std::cout << "Node " << i << " Prob: " << f[i] << "\n";
        }
    }
    return 0;
}

NOIP 实战避坑指南

概率累加时没有对孤立起点或断开节点进行条件拦截 在进行拓扑排序 DP 时，入度为 0 的节点可能不仅包括设定的起点 start_node，还包括其他与主连通块完全断开的孤立死节点。这些死节点的初始概率 f[u] = 0。如果不加控制地用它们的垃圾状态去更新后继，虽不影响数值正确性，但如果涉及复杂的乘除法运算（如求商）则极易产生 NaN（非数）异常。
浮点数精度直接比较的逻辑溃败 在判定概率转移的分支边界时（例如判断某个分支概率是否为 0），绝对不能写成 if (edge.prob == 0.0)。由于计算机内部采用 IEEE 754 浮点数二进制近似存储，连续乘法后的 0 可能会变成 $10^{-17}$ 级别的微小值。必须引入极小量 eps（如 $10^{-9}$）进行范围拦截：if (std::abs(edge.prob) < 1e-9)。

经典 NOIP/洛谷真题

1. 洛谷 P4316 绿豆蛙的归宿

题意描述：给定一个起点为 1，终点为 $N$ 的有向无环图。从起点出发，每到一个节点，会等概率地选择一条出边走下去。求走到终点所经过的路径总长度的数学期望。
问题本质：期望的线性性质与拓扑图条件概率转移。
核心解题思路：虽然该题求的是期望，但其每步转移的系数严格依赖于当前节点的出度。设节点 $u$ 的出度为 $out\_deg[u]$，则走任意一条出边的条件概率均为 $\frac{1}{out\_deg[u]}$。通过反向建图或正向拓扑 DP，将每条边的边权乘以走到当前节点的绝对概率，进行全概率叠加，即可在线性时间内收敛出最终结果。

2. 洛谷 P2218 [HAOI2007] 覆盖问题 / 变式洛谷 P5104 红包发发发

题意描述：某人发了一个总金额为 $w$ 的红包，由 $n$ 个人来抢。每个人抢到的金额是当前剩余总金额在 $(0, 1)$ 区间内的均匀随机分布。求第 $k$ 个人抢到红包金额的期望值。
问题本质：连续型概率空间的条件期望概率推导。
核心解题思路：对于第一个人，抢到金额的期望显然是剩余金额的一半，即 $\frac{w}{2}$，剩下 $\frac{w}{2}$。对于第二个人，面对剩下的 $\frac{w}{2}$，其抢到金额的期望同样是剩下的一半，即 $\frac{w}{4}$。通过数学归纳法容易捕获特征：每个人抢完后，剩余金额的数学期望都会减半。因此第 $k$ 个人抢到金额的期望精确为 $\frac{w}{2^k}$。在代码中直接应用快速幂算出 $2^k$ 在浮点数下的值，做除法即可。