简介
概率
期望
随机变量指示器
给定一个样本空间 $S$ 和一个事件 $A$，定义 $A$ 事件对应的随机变量指示器为：
优势
- 方便概率和期望之间的转换
- 期望线性的性质与随机变量之间是否独立无关
例子
给定一个长度为 $n$ 的随机排列，求逆序对的期望个数
分析：
我们令 $X_{i,j}$ 为事件 $a_i>a_j\wedge i < j$ 的随机变量指示器
那么我们有 $E(X)=E(\sum_{i<j}X_{i,j})=\sum_{i<j}E(X_{i,j})$
那么我们现在就是要求 $X_{i,j}$ 的期望，我们发现由于 $X_{i,j}$ 的取值，我们只需要知道 $X_{i,j}$ 取 $1$ 的概率即可
则 $X_{i,j}=Pr\lbrace a_i
则 $E(X)=\frac{n(n-1)}{4}$
一张 $n\times m$ 的网格图中的每个格子都为黑格或白格
现在将每个白格都染成红色或者蓝色
一块骨牌可以放在两个处于同一行且相邻的红色网格或两个处于同一列且相邻的蓝色网格上
对于一种染法，定义它的价值为能放上的最多骨牌数
求期望价值
CF 1511E Colorings and Dominoes
分析：
我们令 $X_{0}$ 为事件横着放的骨牌的个数的随机变量指示器，$X_1$ 为竖着放的骨牌的个数的随机变量指示器
那么我们有 $E(X)=E(X_0)+E(X_1)$
所以我们可以直接将 $X_0$ 和 $X_1$ 分开求
期望DP的正确性
其实我之前做期望 $dp$ 的时候一直不太理解正确性，即为什么这个状态的期望是上个状态的期望乘上概率的和
其实这个东西就是期望的定义
我们从一道例题来考察一下正确性，poj 2096 Collecting Bugs
首先我们有转移 $f[i][j]=\frac{i}{n}\frac{i}{m}f[i][j]+\frac{n-i}{n}\frac{m-j}{m}f[i+1][j+1]+\frac{n-i}{n}\frac{i}{m}f[i+1][j]+\frac{i}{n}\frac{m-j}{m}f[i][j+1]+1$
我们来思考这样做的正确性，首先对于一个之前的状态，不妨设其为 $f[i+1][j+1]$，我们有 $\frac{n-i}{n}\frac{m-j}{m}$ 的概率可以一步转移到 $f[i][j]$，首先 $f[i+1][j+1]$ 的结构为 $\sum ip_i$，其中 $i$ 表示期望 $i$ 天结束的概率，这个就是期望的定义
那么我们现在考虑，当其转移到 $f[i][j]$ 时，$p_i$ 都要乘上 $\frac{n-i}{n}\frac{m-j}{m}$，然后 $i$ 要变成 $i+1$，我们发现这个比较难处理，但如果考虑所有能转移到 $f[i][j]$ 的状态，发现这些状态到 $i$ 都要变成 $i+1$，而当 $i$ 变成 $i+1$ 时，答案的增量就是 $\sum p_i$，这个东西对于所有状态来说就是 $1$
大概就是这样了
为什么期望DP需要逆推
对于状态 $v$ 来说，不妨设它能转移到的状态为 $w$，能转移到它的状态 $u$
在一般情况下，枚举 $u$ 会比较困难，而枚举 $w$ 则会比较简单
而且如果枚举 $w$ 的话，概率则更难计算
所以一般不会使用顺推
几种期望DP
假期望 $dp$
看起来好像是跟期望有一点关系，但实际上并没有
直接维护 $\sum x_iP(X=x_i)$
这个东西状态转移的时候 $x_i$ 没有变，所以不用加 $1$
简要题意：给定 $n$，以及每个位置出现 $1$ 的概率 $p_i$，求整个 $01$ 串的期望价值
一个 $01$ 串的价值定义为极长的连续 $1$ 的个数的三次方的和
$n\le 10^5$
简要题解：其中 $f$ 维护 $\sum ip_i$，$g$ 维护 $\sum i^2p_i$，$h$ 维护 $\sum i^3p_i$，其中 $p_i$ 表示极长的连续 $1$ 的个数为 $i$ 的期望
$f_i,g_i,h_i$ 分别表示以 $i$ 为起点的极长的连续 $1$ 的个数的一次方、二次方、三次方的期望
通过维护每种权值出现的概率来计算最终的期望
在 $DAG$ 上游走求期望走多少步等价于求到达每个点的概率之和
简要题意：数轴上有 $n + 1$ 个点，分别为 $[0,n]$，你现在在 $0$，从 $i$ 走到 $i+1$ 需要花费 $c_i$ 的时间，有 $p_i$ 的成功概率，$(1-p_i)\frac{w_j}{\sum_{k=1}^iw_k}$ 的概率走到 $i-j(1\le j\le i)$，求走到 $n$ 的期望时间
$n\le 10^5$
简要题解：令 $f_i$ 为从 $i$ 走到 $n$ 的概率，容易得到转移为 $f_i=c_i+p_if_{i+1}+\frac{1-p_i}{\sum_{j=1}^iw_j}\sum_{j=0}^{i-1}f_jw_{i-j}$
注意到后面的 $sum$ 很像是一个分治 $NTT$ 的形式，但是注意到我们的转移成环，但是对于这个形式，我们可以简单移项解决，我们可以得到 $f_{i+1}=\frac{1}{p_i}(f_i-c_i-\frac{1-p_i}{\sum_{j=1}^iw_j}\sum_{j=0}^{i-1}f_jw_{i-j})$，同时我们已知 $f_n=0$，要求 $f_0$，那么我们可以设 $f_i=a_if_0+b_i$，注意到 $a_i$ 和 $b_i$ 之间没有联系，可以直接拆成两个式子，这两个式子都是分治 $NTT$ 的形式，直接做即可，时间复杂度 $O(n\log^2n)$
几个小 trick
如果状态中的某一维是无穷，我们转为考虑那些状态可以转换到最终状态
常见的期望和概率
- 树上随机游走，从 $v$ 走到父亲 $u$ 的期望步数为 $2\times sz_v-1$
例题
简要题意：一开始有 $k$ 个生物，这种生物只能活一天，死亡时有 $p_i,i\in[0,n-1]$ 的概率产生 $i$ 只这种生物，求 $m$ 天内所有生物都死亡的概率
$n,k,m\le 1000$
简要题解：我们令 $f[i]$ 表示一只麻球及其后代在 $i$ 天内全部死掉的概率，注意到每只麻球都可以独立计算
然后我们有以下转移，$f[i]=\sum_{j=0}^{n-1}p[j]f^j[i]$
简要题意：给定一个 $n\times m$ 的网格图，格子有黑色和白色两种，现在你要将每个白色格子染成红色或蓝色，对于每一种染色方案，你需要尽可能的铺上 $1\times 2$ 的骨牌，横着的骨牌必须在两个红色格子上，竖着的骨牌必须在两个蓝色格子上，现在要求所有方案的骨牌数量之和
$n\times m\le 3\times 10^5$
简要题解：首先原题相当于求期望，最后再乘上 $2$ 的若干次方即可
首先根据期望，我们可以将横着的和竖着的拆开了计算
拆开之后，我们只需求横着的若干段的期望和即可，这个东西可以提前预处理
我们令 $f_i$ 表示长度为 $i$ 的期望是多少
容易得到 $f_i=\frac12f_{i-1}+\frac12(\frac12(f_{i-2}+1)+\frac12(f_{i-2+0}))=\frac12(f_{i-1}+f_{i-2}+\frac14)$
时间复杂度 $O(n\times m)$
简要题意：给定一棵 $n$ 个点以 $1$ 为根的树，现在随机使 $k$ 条边变成单向边，方向为从儿子指向父亲，问从 $s$ 出发随机游走到 $1$ 的期望步数
$n\le 10^6$
简要题解：如果我们不考虑随机将 $k$ 条边定向，那么这就是一个经典问题，我们从 $v$ 走到父亲 $u$ 的期望步数为 $2sz_v-1$，我们定义从 $s$ 走到 $1$ 的这条路径为 $L$，同时规定 $L$ 不包含 $1$，那么答案就是 $\sum_{u\in L}(2sz_u-1)$
我们考虑将边定向，如果 $(v,u)$ 这条边在路径 $L$ 上，我们将 $(v,u)$ 这条边定向，那么相当于将 $u$ 的子树大小减掉 $sz_v$，不妨令 $u$ 的父亲为 $a$，那么如果 $(u,a)$ 这条边没有被定向，那么 $a$ 的子树大小也要减掉 $sz_v$，所以 $(v,u)$ 这条边的贡献大概是一个组合数前缀和的形式；如果 $(v,u)$ 不在路径上，我们只需要把它贡献到它在路径上的第一个祖先的位置即可，贡献的系数同样也是一个组合数前缀和的形式，时间复杂度 $O(n)$
简要题意：现在有 $n$ 个人围成一圈进行游戏，游戏规则为每一轮在 $n$ 个人中随机抽取一个人使其出局，如果抽到的人已经出局，则顺延到下一个人，现在游戏已经进行了 $n-k$ 轮，还剩下 $k$ 个人，告诉你 $k$ 个人的编号，现在游戏继续进行，如果 $s$ 出局则结束，问游戏期望进行多少轮
$n\le 10^9,k\le 200$
简要题解：我们令还活着的人的前面的已经出局的人的个数为 $a_i$，这里需要注意这 $n$ 个人成环，容易得到 $\sum a_i=n$，同时第 $i$ 个人出局的概率为 $\frac{a_i}{n}$，为了去掉环的限制，我们将 $s$ 移到 $a_k$
答案需要求期望进行多少轮，我们将答案转换为求到达每个状态的概率之和，我们思考任意一个合法状态的形态如何，显然是将 $a_1$ 到 $a_k$ 分成若干段，每一段只有右端点还活着，那么我们利用这个进行 $dp$，我们令 $f_{i,j}$ 表示前 $i$ 个，分成了 $j$ 段，这里记录 $j$ 是因为我们需要知道进行了多少轮，因为我们记录的概率是是所有操作序列的概率和，这东西是有顺序的，所以在合并的时候要乘上一个组合数，容易得到转移式 $f_{i,j}=\sum_{k<i}f_{k,j-1}\binom{i-j}{k-(j-1)}g_{k+1,i}$ 其中 $g_{i,j}$ 表示将 $[i,j]$ 合并的概率，这个东西可以用区间 $dp$ 计算
总时间复杂度 $O(k^3)$
2022-2023 ICPC NERC (NEERC), North-Western Russia Regional Contest (Northern Subregionals) I IQ Game