「学习笔记」概率和期望

点击查看目录
目录

我不知道这篇学习笔记和杂题乱写有什么区别。

前几道题推的时候没在云剪贴板备份，不写了。

例题

P1850 [NOIP2016 提高组] 换教室

\(f_{i, j, 0/1}\) 表示第 \(i\) 节课换了 \(j\) 次，当前在原来的/现在的教室的体力值。

\[\begin{aligned}
&f_{i, j, 0} = \min
\begin{cases}
f_{i - 1, j, 0} + tu_{w, x}\\
f_{i - 1, j, 1} + tu_{w, x} * (1 - p_{i-1}) + tu_{z, x} * p_{i-1}\\
\end{cases}\\ \ \\

&f_{i, j, 1} = \min
\begin{cases}
f_{i - 1, j - 1, 0} + tu_{w, x} * (1 - p_{i}) + tu_{w, y} * p_{i}\\
f_{i - 1, j - 1, 1} + tu_{w, x} * (1 - p_{i-1}) * (1 - p_{i}) + tu_{z, x} * p_{i-1} * (1 - p_{i}) + tu_{w, y} * (1 - p_{i-1}) * p_{i} + tu_{z, y} * p_{i-1} * p_{i}\\
\end{cases}\\
\end{aligned}
\]

P2473 [SCOI2008] 奖励关

\(f_{i, st}\) 表示第 \(i\) 次抛出前集合状态为 \(st\) 时，吃或不吃的之后的宝物的期望分值。

\[f_{i, st} = \sum_{j = 1}^{n}\dfrac{[s_j\in st]\max\{f_{i + 1, st}, f_{i + 1, sta} + p_j\} + [s_j\not\in st]f_{i + 1, st}}{n}
\]

P4284 [SHOI2014] 概率充电器

\(f_{i}\) 表示 \(i\) 能被子树或自己充不上的概率，\(g_{i}\) 表示 \(i\) 能被父亲充不上的概率。

\[\begin{aligned}
f_{i} &= \prod_{j \in son_i} (1 - w_{i, j} \times (1 - f_j)) \times (1-p_i)\\
g_{i} &= 1 - (1 - g_{fa_i} \times \frac{f_{fa_i}}{1 - w_{i, fa_i} \times (1 - f_i)}) \times w_{i, fa_i}
\end{aligned}
\]

P3232 [HNOI2013]游走

显然使用贪心，一条边被经过期望次数越少编号越大。

那么如何算出一条边被经过期望次数？设 \(f_i\) 为点 \(i\) 被经过的次数，\(e_i\) 表示点 \(i\) 的边数，那么一个点只要不是点 \(n\)，每次被经过后都会选一个边出去，则边 \((u, v)\) 被期望经过次数为 \(\dfrac{f_u}{e_u} + \dfrac{f_v}{e_v}\)。

列出 \(f_i\) 的转移方程：

\[f_i = [i=1] + \sum_{(i,j)\in\mathbb{E}}\frac{f_j}{e_j}\\
\]

发现没法直接转移，那么使用高斯消元。

移一下项：

\[f_i - \sum_{(i,j)\in\mathbb{E}}\frac{f_j}{e_j} = [i=1]
\]

列出增广矩阵：

\[\left[
\begin{matrix}
1&-\frac{[(1,2)\in\mathbb{E}]}{e_2}&-\frac{[(1,3)\in\mathbb{E}]}{e_3}&\cdots&-\frac{[(1,n-1)\in\mathbb{E}]}{e_{n-1}}\\\\
-\frac{[(2,1)\in\mathbb{E}]}{e_1}&1&-\frac{[(2,3)\in\mathbb{E}]}{e_i}&\cdots&-\frac{[(2,n-1)\in\mathbb{E}]}{e_{n-1}}\\\\
\cdots&\cdots&\cdots&\cdots&\cdots\\\\
-\frac{[(n-1,1)\in\mathbb{E}]}{e_1}&-\frac{[(n-1,2)\in\mathbb{E}]}{e_2}&-\frac{[(n-1,3)\in\mathbb{E}]}{e_3}&\cdots&1
\end{matrix}
\middle|
\begin{matrix}
1\\\\
0\\\\
\cdots\\\\
0\\
\end{matrix}
\right]
\]

直接高斯消元即可。

P3211 [HNOI2011]XOR和路径

\(f_{i, k}\) 表示第 \(i\) 个点到 \(n\) 的期望异或和的第 \(j\) 位的期望值（即为 \(1\) 的概率）。

为什么要选择逆推？因为可能有自环，顺推时我们无法确定点 \(f_{1, k}\) 是 \(1\) 还是 \(0\)，但是逆推时可以确定 \(f_{n, k} = 1\)。

那么此时：

\[f_{i, k} = \sum_{(i, j)\in\mathbb{E}}\frac{(1-w(i,j)_k)f_{j, k} + w(i,j)_k(1 - f_{j, k})}{d_i}
\]

移个项：

\[\begin{aligned}
&f_{i, k} = \sum_{(i, j)\in\mathbb{E}}\frac{(1-w(i,j)_k)f_{j, k}}{d_i} + \sum_{(i, j)\in\mathbb{E}}\frac{w(i,j)_k}{d_i} + \sum_{(i, j)\in\mathbb{E}}\frac{-w(i,j)_kf_{j, k}}{d_i}\\
&f_{i, k} + \sum_{(i, j)\in\mathbb{E}}\frac{w(i,j)_kf_{j, k}}{d_i} - \sum_{(i, j)\in\mathbb{E}}\frac{(1-w(i,j)_k)f_{j, k}}{d_i} = \sum_{(i, j)\in\mathbb{E}}\frac{w(i,j)_k}{d_i}\\
&f_{i, k} + \sum_{(i, j)\in\mathbb{E}}\frac{(2w(i,j)_k - 1)f_{j, k}}{d_i} = \sum_{(i, j)\in\mathbb{E}}\frac{w(i,j)_k}{d_i}\\
&d_if_{i, k} + \sum_{(i, j)\in\mathbb{E}}(2w(i,j)_k - 1)f_{j, k} = \sum_{(i, j)\in\mathbb{E}}w(i,j)\\
\end{aligned}
\]

冲几个高斯消元即可。

最后答案为：

\[\sum_{i = 0}^{31}f_{n,i}\times2^{i}
\]

P3750 [六省联考 2017] 分手是祝愿

首先比较显然的是最优策略是从 \(n\) 到 \(1\) 看到亮的就按掉。

不难发现最优策略中按下的按键顺序不定，只要都按过就可以。如果按了一个错误的按键，必须再按回去，因为最优策略并不包含这个键，只有再按一次这个键才能用最少次数（\(1\) 次）抵消其负面效果。

那么 \(f_{i}\) 表示需要再正确地按 \(i\) 次到需要再正确地按 \(i - 1\) 次的期望步数。

\[\begin{aligned}
f_{i} &= 1\times\frac{i}{n} + (1 + f_{i + 1} + f_{i})\times\frac{n-i}{n}\\
f_{i} &= 1 + \frac{n-i}{n}f_{i + 1} + \frac{n-i}{n}f_{i}\\
\frac{i}{n}f_{i} &= 1 + \frac{n-i}{n}f_{i + 1}\\
f_{i} &= \frac{n}{i} + \frac{n-i}{i}f_{i + 1}\\
\end{aligned}
\]

P3706 [SDOI2017]硬币游戏

首先为了方便，我们把“不包含任意一个同学猜的串的字符串”称为“合法串”。

\(f_i\) 表示第 \(i\) 个同学胜利的概率，\(f_0\) 表示任意长度的一个串为合法串的概率。

一个很显然的性质是，第 \(i\) 个同学胜利时的字符串一定是一个合法串加上第 \(i\) 个同学猜的串，其概率为 \(\dfrac{f_0}{2^{m}}\)。

但是 \(f_i\) 并不等于这个数，因为一个合法串的后缀和第 \(i\) 个同学猜的串的前缀可能可以组成一个别的同学猜的串！这个时候就不是第 \(i\) 个同学胜利了。

那么我们考虑算出这种情况的概率，令 \(f_0\) 与之相减即可得到 \(f_i\)。

设 \(pre_{i,j}\) 表示第 \(i\) 个同学猜的串的长度为 \(j\) 的前缀，\(suf_{i,j}\) 表示第 \(i\) 个同学猜的串的长度为 \(j\) 的后缀。

\[f_i + \sum_{j = 1}^{n}f_j\sum_{k = 1}^{m}[pre_{i, k} = suf_{j, k}]\dfrac{1}{2^{m - k}} = \dfrac{f_0}{2^{m}}\\
\]

然后冲一个高斯消元即可。

树

梦游中的你来到了一棵 \(N\) 个节点的树上。你一共做了 \(Q\) 个梦，每个梦需要你从点 \(u\) 走到点 \(v\) 之后才能苏醒。由于你正在梦游，所以每到一个节点后，你会在它连出去的边中等概率地选择一条走过去，为了确保第二天能够准时到校，你要求出每个梦期望经过多少条边才能苏醒。为了避免精度误差，你要输出答案模 \(10^9 + 7\) 的结果。

\(f_i\) 表示从 \(i\) 走到其父亲的期望步数，\(g_i\) 表示从其父亲走到 \(i\) 的期望步数，\(d_i\) 表示与 \(i\) 相连的点数。

\[\begin{aligned}
f_i &= \frac{1}{d_i} + \sum_{j\in son_i}\frac{f_j + f_i + 1}{d_i}\\
g_i &= \frac{1}{d_{fa_i}} + \sum_{j\in son_{fa_i} \wedge j\not=i}\frac{g_i + f_j + 1}{d_{fa_i}} + \frac{g_i + g_{fa_i} + 1}{d_{fa_i}}
\end{aligned}
\]

化简一下：

\[\begin{aligned}
f_i &= 1 + \frac{1}{d_i}\sum_{j\in son_i}f_j + \frac{(d_i - 1)f_i}{d_i}\\
g_i &= 1 + \frac{1}{d_{fa_i}}\sum_{j\in son_{fa_i} \wedge j\not=i}f_j + \frac{g_{fa_i}}{d_{fa_i}} + \frac{(d_i - 1)g_i}{d_{fa_i}}
\end{aligned}
\]

再进行一个移项。

\[\begin{aligned}
f_i - \frac{(d_i - 1)f_i}{d_i} &= 1 + \frac{1}{d_i}\sum_{j\in son_i}f_j\\
\frac{f_i}{d_i} &= 1 + \frac{1}{d_i}\sum_{j\in son_i}f_j\\
f_i &= d_i + \sum_{j\in son_i}f_j\\
\end{aligned}
\]

\[\begin{aligned}
g_i - \frac{(d_i - 1)g_i}{d_{fa_i}} &= 1 + \frac{1}{d_{fa_i}}\sum_{j\in son_{fa_i} \wedge j\not=i}f_j + \frac{g_{fa_i}}{d_{fa_i}}\\
\frac{g_i}{d_{fa_i}} &= 1 + \frac{1}{d_{fa_i}}\sum_{j\in son_{fa_i} \wedge j\not=i}f_j + \frac{g_{fa_i}}{d_{fa_i}}\\
g_i &= d_{fa_i} + \sum_{j\in son_{fa_i} \wedge j\not=i}f_j + g_{fa_i}\\
g_i &= f_{fa_i} - f_i + g_{fa_i}\\
\end{aligned}
\]

啊为什么这个题要写树剖这么麻烦的东西啊？哦原来有个东西叫前缀和啊。

\[\Huge\mathfrak{The End}
\]