期望：是对一个随机事件的结果的平均值的估计。
例如说：有一个游戏：抛硬币，正面赚 100 元，反面赔 100 元，你会觉得这个游戏不赚不赔，这个游戏的期望就是 0.
又有一个游戏：正面赚 100 元，反面赔 50 元，你会觉得这个游戏稳赚不赔，你会发现，有 \(\frac 12\) 的概率赚 100，\(\frac 12\) 的概率赔 50，期望为：\(\frac 12 \times 100 + \frac 12 \times (-50) = 25\)。
离散期望
基础概念
定义 1.1：设 \(E\) 是一个随机事件集，\(V(e)\) 是 \(e\) 事件的结果，\(P(e)\) 是 \(e\) 事件的发生概率，则期望被定义为：
\[\mathcal E(S;V,P) = \sum\limits_{e \in S} V(e) P(e) \]，例如上面的游戏 2：\(\mathcal E = V(正面)P(正面)+V(反面)P(反面) = \frac 12 \times 100 + \frac 12 \times (-50) = 25\)
，再例如，一个均匀的六面骰子的期望点数是：\(\mathcal E(\{1,2,3,4,5,6\}) = V(1)P(1)+V(2)P(2)+\dots+V(6)P(6)=\frac 16 (1+2+3+4+5+6)=\frac 72\)。
一个经典的例题：有一枚硬币，抛出正面你赚一块钱，并可以继续抛；抛出反面终止游戏。求期望。请思考一下。
考虑在哪一次出现了反面。
- 反：概率 1/2，赚 0 元
- 正反：概率 1/4，赚 1 元
- 正正反：概率 1/8，赚 2 元
- 正...正（n个）反：概率 1/2n+1，赚 n 元。
所以期望值为：
\[\mathcal E(\{反,正反,\dots\}) = \sum\limits_{i=0}^{+\infty} \dfrac i{2^{i+1}} = \sum\limits_{i=1}^{+\infty} \dfrac i{2^{i+1}} \]这是一个无穷级数的求和，考虑错位相减
\[\frac {\mathcal E} 2 = \sum\limits_{i=0}^{+\infty} \dfrac i{2^{i+2}} = \sum\limits_{i=1}^{+\infty} \dfrac {i-1}{2^{i+1}} \]\[\mathcal E - \frac {\mathcal E} 2 = \sum\limits_{i=1}^{+\infty} \dfrac 1{2^{i+1}} = \dfrac 12 \]\[\mathcal E = 1 \]定理 1.1：期望具有可数乘性、可乘性。即
\[\mathcal E(\{a\}; C, 1) = C \]\[\mathcal E(A; k \times V, P) = k \times \mathcal E(A; V, P) \]\[\mathcal E(A_1 \times A_2; V_1 \times V_2, P_1 \times P_2) = \mathcal E(A_1; V_1, P_1) \times \mathcal E(A_2; V_2, P_2) \]\[\mathcal E(A_1 + A_2; V_1 + V_2, P_1 + P_2) = \mathcal E(A_1; V_1, P_1) + \mathcal E(A_2; V_2, P_2) \]。定义 1.1
期望 DP
Problem 1: [https://atcoder.jp/contests/abc280/tasks/abc280_e](ABC 280 E)
题意：设有一序列 \(a\) 满足 \(a_0 = n\)，有
- \(p\%\) 的概率 \(a_{i+1} = a_i - 2\)
- \((100-p)\%\) 的概率 \(a_{i+1} = a_i - 1\)
求 \(a\) 的大于零部分的期望长度。时间复杂度要求 \(\mathcal O(n)\)。
设函数 \(f(x)\) 表示 \(a_0 = x\) 的大于零部分的期望长度。
注意到首先去掉 \(a_0\)，把 \(a_1\) 当作 \(a'_0\)，则有 \(f(a_0) = 1 + f(a_1)\)。
考虑到 \(a_1 = \left\{\begin{matrix}a_0 - 2 & p\% \\ a_0 - 1 & (100-p)\%\end{matrix}\right.\)，有 \(f(x) = 1 + p\% f(x - 2) + (1-p\%) f(x - 1)\)。
动态规划即可。
Problem 2: Problem 1 变体
题意：设有一序列 \(a\) 满足 \(a_0 = n\)，有
- \(p\%\) 的概率 \(a_{i+1} = a_i - 0\)
- \((100-p)\%\) 的概率 \(a_{i+1} = a_i - 1\)
求 \(a\) 的大于零部分的期望长度。时间复杂度要求 \(\mathcal O(n)\)。
同样设函数 \(f(x)\)，得到 \(f(x) = 1 + p\% f(x) + (100 - p)\% f(x - 1)\)，解方程得到 \(f(x) = f(x-1) + \dfrac{100}{100 - p}\)。（显然又有 \(f(x) = x \times \dfrac{100}{100 - p}\)）
Problem 3: Problem 1 变体
题意：设有一序列 \(a\) 满足 \(a_0 = n\)，有
- \(\dfrac 1m\) 的概率 \(a_{i+1} = a_i - 1\)
- \(\dfrac 1m\) 的概率 \(a_{i+1} = a_i - 2\)
- ...
- \(\dfrac 1m\) 的概率 \(a_{i+1} = a_i - m\)
求 \(a\) 的大于零部分的期望长度。保证 \(\sum p = 100\)、时间复杂度要求 \(\mathcal O(n)\)。
同样设 \(f(x)\)，得到柿子：
，其中 \(Q\) 是前缀和数组。
代码差不多就是这样的：
Z f[N], Q_[N * 2];
Z *Q = Q_ + N;
int main() {
for (int i = 1; i <= n; ++ i) {
f[i] = 1 + (Q[i - 1] - Q[i - m]) / m;
Q[i] = Q[i + 1] + f[i];
}
cout << f[n] << endl;
}
/*
* 有可能 i - m < 0，所以进行下标负数化处理。
*/
Problem 4: ABC 271 G
设数组 \(p\) 满足 \(p\) 是 T 或 A 访问的概率。则一天内不访问的概率是：
。
设函数 \(f(x, y)\) 代表 \(x:00\) 访问了 \(y\) 次