利用期望的线性性质优化随机步进问题的解法

核心逻辑与数学原理

数学期望（Mathematical Expectation）是离散随机变量所有可能取值的加权平均数。设离散随机变量 $X$ 的可能取值为 $x_1, x_2, \dots, x_n$，对应发生的概率为 $p_1, p_2, \dots, p_n$，则 $X$ 的数学期望定义为：

$$E(X) = \sum_{i=1}^n x_i \cdot p_i$$

在 NOIP 级别的组合计数与概率题中，期望的线性性质（Linearity of Expectation）是斩断复杂状态关联的最高效利器。对于任意两个相互独立的或强耦合、不独立的随机变量 $X$ 和 $Y$，均严格满足：

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

推广到 $n$ 个随机变量的情形：

$$E\left( \sum_{i=1}^n X_i \right) = \sum_{i=1}^n E(X_i)$$

破局机理分析

在竞赛得分或代价统计题中，总得分 $X$ 往往由许多局部动作（如每一步是否得分、每一对逆序对是否存在）复合而成。由于动作之间通常存在复杂的后续影响，直接求解总状态的概率分布极其困难。

利用期望的线性性质，我们可以采取示性变量拆解法：

将总贡献 $X$ 拆分为 $n$ 个局部极小代价之和：$X = X_1 + X_2 + \dots + X_n$。
这里的 $X_i$ 通常设计为 $0/1$ 示性随机变量（即动作成功取 $1$，失败取 $0$）。
此时 $E(X_i) = 1 \cdot P(X_i=1) + 0 \cdot P(X_i=0) = P(X_i=1)$。
绕过整体复杂的联合概率分布，只需独立求解每个局部动作发生的绝对概率 $P(X_i=1)$，求和即为总期望。

状态设计与算法推导

序列随机游走代价的状态设计

设有一个序列或图结构，我们在其上进行随机步进，求某种代数指标的期望值。

以“随机击中目标所需的步数”为例。设从状态 $i$ 转移到状态 $i+1$ 的成功概率为 $p_i$，失败则退回到状态 $0$。若直接设计全局期望，状态之间会因“退回”产生复杂的循环依赖。

利用期望的线性性质，定义状态变量 $\Delta E[i]$ 表示从状态 $i$ 第一次转移到状态 $i+1$ 的期望步数。根据单步转移的分支归纳：

分支 A：一步成功，概率为 $p_i$，代价为 $1$ 步。
分支 B：失败退回状态 $0$，概率为 $1 - p_i$。此时所需代价为：当前耗费的 $1$ 步 + 从状态 $0$ 重新打回状态 $i$ 的期望步数 + 从状态 $i$ 迈向 $i+1$ 的期望步数。

由期望的定义列出方程：

$$\Delta E[i] = p_i \cdot 1 + (1 - p_i) \cdot \left( 1 + \sum_{j=0}^{i-1} \Delta E[j] + \Delta E[i] \right)$$

对方程进行代数变形，将等式右侧的 $\Delta E[i]$ 移项到左侧提取系数：

$$\Delta E[i] - (1 - p_i) \Delta E[i] = p_i + (1 - p_i) \left( 1 + \sum_{j=0}^{i-1} \Delta E[j] \right)$$

$$p_i \cdot \Delta E[i] = 1 + (1 - p_i) \sum_{j=0}^{i-1} \Delta E[j]$$

$$\Delta E[i] = \frac{1 + (1 - p_i) \sum_{j=0}^{i-1} \Delta E[j]}{p_i}$$

利用前缀和数组 $sum[i] = \sum_{j=0}^{i-1} \Delta E[j]$ 优化累加。状态转移方程坍缩为：

$$\Delta E[i] = \frac{1 + (1 - p_i) \cdot sum[i]}{p_i}$$

最终从状态 $0$ 走到终点 $N$ 的总期望步数即为 $\sum_{i=0}^{N-1} \Delta E[i]$。完美将多步依赖拉平为 $O(N)$ 线性递推。

C++ 标准源码

#include <iostream>
#include <vector>

const int MOD = 998244353; // 常规数论期望题要求对大质数取模输出

// 费马小定理求逆元
long long quick_power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

long long get_inv(long long n) {
    return quick_power(n, MOD - 2);
}

// 求解随机步进模意义下的总期望步数
long long solve_expectation_walk(int n, const std::vector<long long> &p_num, const std::vector<long long> &p_den) {
    std::vector<long long> delta_E(n);
    long long prefix_sum = 0; // 维持当前的 sum[i] 状态

    for (int i = 0; i < n; ++i) {
        // 计算当前位置的概率 p_i = p_num[i] / p_den[i] 的模意义数值
        long long p = p_num[i] * get_inv(p_den[i]) % MOD;
        long long 一减p = (MOD + 1 - p) % MOD;

        // 分子部分: 1 + (1 - p_i) * sum[i]
        long long numerator = (1 + 一减p * prefix_sum) % MOD;

        // 单步期望 delta_E[i] = numerator / p_i
        delta_E[i] = numerator * get_inv(p) % MOD;

        // 动态更新前缀和，为下一层状态服务
        prefix_sum = (prefix_sum + delta_E[i]) % MOD;
    }

    long long total_expectation = 0;
    for (int i = 0; i < n; ++i) {
        total_expectation = (total_expectation + delta_E[i]) % MOD;
    }
    return total_expectation;
}

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

    int n;
    if (std::cin >> n) {
        std::vector<long long> p_num(n), p_den(n);
        for (int i = 0; i < n; ++i) {
            std::cin >> p_num[i] >> p_den[i]; // 读入概率的分子与分母
        }
        std::cout << solve_expectation_walk(n, p_num, p_den) << "\n";
    }
    return 0;
}

NOIP 实战避坑指南

错将非独立随机变量的乘积期望等同于期望的乘积 选手常因过度迷信线性性质而衍生出致命错误：认为 $E(X \cdot Y) = E(X) \cdot E(Y)$。注意：期望的乘法性质只有在 $X$ 和 $Y$ 严格相互独立时才成立。如果两状态有因果关联，必须通过条件期望或联合状态转移来维护，绝不可直接拆分乘积。
模意义下期望计算出现负数分母 在求 (MOD + 1 - p) % MOD 时，若直接写成 1 - p % MOD，结果在 C++ 中大概率会变成负数。这会导致后续乘以逆元时数据直接溢出，算出一个天文数字。必须通过加上 MOD 强制校正为非负正数。

经典 NOIP/洛谷真题

1. 洛谷 P1365 WJMZBMR打雪仗 / 类似洛谷 P1654 OSU!

题意描述：给定一个长度为 $n$ 的操作序列，每个位置可能是成功 o（贡献 1 分）、失败 x（不得分）或未知的 ?（等概率为 o 或 x）。连续成功 $x$ 次可以获得 $x^2$ 的收益。求最终总收益的数学期望。
问题本质：高次随机变量的期望拆解与线性递推。
核心解题思路：因为期望不满足 $E(X^2) = E(X)^2$，我们无法直接维护得分的平方期望。但根据 $(len + 1)^2 = len^2 + 2 \cdot len + 1$，我们可以利用期望的线性性质，同时维护两个一维状态：当前连续成功的长度期望 $E(len)$ 和当前的总得分期望 $E(score)$。当遇到成功概率为 $p$ 的节点时，状态转移方程为：

$$E(len)_{\text{new}} = p \cdot (E(len) + 1)$$

$$E(score)_{\text{new}} = E(score) + p \cdot (2 \cdot E(len) + 1)$$

由于成功长度是一次的，满足线性关系，通过这样层层解耦，即可在 $O(N)$ 时间内完成对二次项总收益期望的精确求解。

2. 洛谷 P3802 纯净的雪

题意描述：共有 $7$ 种属性的特殊道具，数量分别为 $a_1, a_2, \dots, a_7$。现在将这些道具随机打乱排成一列。如果连续 $7$ 个道具恰好各不相同，就会触发一次特殊效果。求触发特殊效果次数的数学期望。
问题本质：示性变量拆解法的极限落地。
核心解题思路：设总道具数为 $N = \sum a_i$。总共可以形成 $N - 6$ 个长度为 $7$ 的连续区间。由于期望满足线性性质，总触发次数的期望等于每个区间触发效果的概率之和。因为排列的对称性，任何一个长度为 $7$ 的区间触发该效果的概率是完全均等的。对于任意固定区间，其 $7$ 个元素各不相同的概率为：

$$P = \frac{a_1}{N} \cdot \frac{a_2}{N-1} \dots \cdot \frac{a_7}{N-6} \cdot 7!$$

因此，总期望直接等于 $(N - 6) \cdot P$。甚至不需要运行任何循环 DP，通过一记精纯的代数公式即可在 $O(1)$ 时间内破局。