【复习】概率期望做题笔记

胡做八做了一点简单的期望题,算是练练手感吧。

一共是 $15$ 道题。

不太需要技巧的例题

Luogu3802 小魔女帕琪

这东西我硬推推出来一个:

的东西。感觉还可以?然后其实就是一种思想?此时总方案数$\rm S$这东西不应该除以某些奇怪的阶乘,或者说,不需要,因为样本空间可以理解为先发生了$A$和发生了$B$虽然局面一样但是概率独立(大概

Luogu5489 [LnOI2019]脸滚键盘

这题写过题解,现在复习一遍。大概就是考虑维护一个前缀和,构造数列

然后我们发现它的级数很美妙:

正好就是我们要求的答案。

但此时直接前缀和会有问题,因为多余的实际上是$a_0\cdots a_n$那一堆项,所以需要像哈希一样左半边乘上

Luogu1297 [国家集训队]单选错位

然后其实,$\rm E_S=\mathbb{E}(1)+\mathbb{E}(2)+\mathbb{E}(3)\cdots$

观察 $ \mathbb{E}(i)$,实际上只与 $ base_i,base_{i+1}$ 有关,那么每一项的贡献就是 $\dfrac{1}{\max(base_i,base_{i+1})}$。加起来即可。

Luogu3924 康娜的线段树

每次在线段树区间加操作做完后,从根节点开始等概率的选择一个子节点进入,直到进入叶子结点为止,将一路经过的节点权值累加,最后能得到的期望值是多少?

此处的区间加是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Segment_Tree{
#define lson (o<<1)
#define rson (o<<1|1)
int sumv[N<<2],minv[N<<2];
inline void pushu\Pr(int o){sumv[o]=sumv[lson]+sumv[rson];}
inline void build(int o,int l,int r){
if(l==r){sumv[o]=a[l];return;}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushu\Pr(o);
}
inline void change(int o,int l,int r,int q,int v){
if(l==r){sumv[o]+=v;return;}
int mid=(l+r)>>1;
if(q<=mid)change(lson,l,mid,q,v);
else change(rson,mid+1,r,q,v);
pushu\Pr(o);
}
}T;
//区间加
for(int i=l;i<=r;i++)T.change(1,1,n,i,addv);

$1\leq n,m\leq 10^6$ 。

根据线性性显然可以知道维护的就是

其中根节点的 $depth$ 默认为 $0$ 。考虑先把这个式子通分一下:

然后考虑,如果是区间修改,那么本质上只需要求出区间内所有点的线段树上子树内系数 $2^{maxL-depth_i}$ 的和。这一部分可以直接预处理得到。并且考虑只有区间加的操作,所以并不需要真正动态地去维护。直接维护一个全局 $ans$ 即可。

于是最后复杂度线性。

考察期望线性性的题目

[ZROI 1142]石子

小 D 正在玩取石子游戏。 小 D 共有 $n$ 堆石子,依次编号为 $1, 2, · · · , n$,其中第 $i$ 堆有 $a_i$ 颗石子。 小 D 每次会等概率随机选择一颗石子,并取完它所在的那一堆石子。 小 D 想要知道,第 $1$ 堆石子被取走的时间的期望。

$n=10^6$。

根据期望的线性性,可以知道可以分别算每堆石子在第 $1$ 堆之前被取完的概率。所以就是

于是代码:

1
2
3
4
5
6
7
int main(){
cin >> N ; int i ; ans = 1 ;
for (i = 1 ; i <= N ; ++ i) cin >> base[i] ;
for (i = 2 ; i <= N ; ++ i)
ans += (double)base[i] / (double)(base[i] + base[1]) ;
printf("%.9lf", ans) ;
}

[BZOJ3036]绿豆蛙的归宿

给出 $n$ 个点 $m$ 条边的有向无环图,起点为 $1$,终点为 $n$,每条边都有一个长度,并且从起点出发能够到达所有的点,所有的点也都能够到达终点。

绿豆蛙从起点出发,走向终点。 到达每一个顶点时,如果该节点有 $k$ 条出边,绿豆蛙可以选择任意一条边离开该点,并且走向每条边的概率为 $\dfrac{1}{k}$ 。现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?

发现路径可以拆分,于是根据期望的线性性有

于是 dfs 一遍即可。

CF280C Game On Tree

给出一棵树,每次随机等概率选择一未染黑的点,将它及其子树染黑。问期望多少次操作可以将树全部染黑。

$1\leq n\leq 10^5$ .

草,我居然能把这题给秒掉,太可怕了。

考虑首先是期望的线性嘛,于是可以知道 $\mathbb{E}(T)$ 表示把树 $T$ 全部染黑的期望次数,那么可以知道有

其中 $u$ 是那么考虑如果想要染黑一棵以 $u$ 为根的子树,可以采用的策略是把它到根的路径上任意一点染黑,但是只有在染黑他自己的时候才会对答案产生贡献。所以不难知道

考察转移递推思想的期望题目

[NOI2005]聪聪与可可

给定一张 $n,m$ 的无向图。两个人一开始分别在点 $A,B$。每次 $A$ 先走,$B$ 后走,$A$ 每次会选择一个离 $B$ 最近且编号最小的点走 $1\sim2$ 步,$B$ 随机游走(也可停在原地,概率平摊),求期望多少步 $A$ 可以与 $B$ 相遇。

$1 \leq N, E \leq 1000$。

emmm 要是化归子问题的话,一开始觉得应该算出在每个点相遇的期望步数,但想了想觉得这个并不可做…

于是考虑更暴力一点化归子问题: $f_{u,v}$ 表示 $A$ 在 $u$,$B$ 在 $v$ 时两者相遇的期望步数。那么考虑转移:

1、$u=v$ ,$f_{u,v}=0$ 。

2、$dis(u,v)=1$,$f_{u,v}=1$ (因为 $A$ 先走)。

3、$dis(u,v)>1$,$f_{u,v}=\dfrac{\sum{f_{u’,v’}}}{\deg(v)+1}$ ,其中 $u’$ 是 $u$ 走两步可以到达的离 $v$ 最近的一个点,$v$ 是随便一个点。

然后就可以记搜了。我其实很迷惑为什么全员最短路的题要出 $1e3$ …除了强行丰富代码难度,有什么意义吗…

注意实现的一点小细节。如果 $x$ 走两步就可以走到 $y$,此时应该直接 return 1.0 ,因为 $B$ 根本没有走的机会。

[LuoguP1365]OSU!(Easy Version)

给定一个序列,某些位置是 $0$,某些位置是 $1$ ,某些位置分别有 $50\%$ 的概率变成 $0$ 或者 $1$ 。求极大连续纯 $1$ 段的长度的平方之和的期望。

$1\leq n\leq 10^6$ 。

考虑分别记 $f_i,g_i$ 表示总期望/当前段的期望。那么可以分类讨论 $i$ 的类型:

1、$a_i=1,g_i=g_{i-1}+1,f_{i}=f_{i-1}+2\cdot g_{i-1}+1$ 。

2、$a_i=0,g_i=0,f_{i}=f_{i-1}$ 。

3、$a_i=?,g_{i}=g_{i-1}+0.5,f_{i}=f_{i-1}+g_{i-1}+0.5$ 。

还是比较简单的。注意一个点即可,根据期望的线性性,如果按照「前 $i$ 个」作为划分阶段的依据,需要把一个极长连续 $1$ 段的贡献摊到每个元素上面,摊的方法就是平方和公式。

[BZOJ4318]OSU!(Hard Version)

我们可以把osu的规则简化与改编成以下的样子:

一共有 $n$ 次操作,每次操作只有成功与失败之分,成功对应1,失败对应0,$n$ 次操作对应为长度为 $n$ 的01 串。在这个串中连续的 $X$ 个 1 可以贡献 $X^3$ 的分数,这 $X$ 个 $1$ 不能被其他连续的 $1$ 所包含(也就是极长的一串1)

现在给出 $n$,以及每个操作的成功率,请你输出期望分数。

$1\leq n\leq 10^6$ 。

跟上一题十分接近的思路。但是考虑立方和公式 $(x+1)^3=x^3+3x^2+3x+1$ ,由于 $\mathbb{E}^2(x)\neq \mathbb{E}(x^2)$,所以不能直接拿线性性拆。于是考虑分别维护极长段的平方和和长度即可。

1
2
3
4
5
for (i = 1 ; i <= N ; ++ i){
g[i] = (g[i - 1] + 1) * base[i],
p[i] = (p[i - 1] + 2 * g[i - 1] + 1) * base[i],
f[i] = f[i - 1] + base[i] * (3 * p[i - 1] + 3 * g[i - 1] + 1) ;
}

[Luogu4550]收集邮票

有 $n$ 种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一张,并且买到的邮票究竟是 $n$ 种邮票中的哪一种是等概率的,概率均为 $\dfrac{1}{n}$。但是由于凡凡也很喜欢邮票,所以皮皮购买第 $k$ 张邮票需要支付 $k$ 元钱。

现在皮皮手中没有邮票,皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

$1\leq n\leq 10^6$ 。

首先考虑一个简化版问题:

每次随机一个$[1,n]$的整数,问期望几次能凑出所有数

考虑期望的线性性,就是 $\mathbb{E}=\sum \mathbb{E}(i)$,其中 $\mathbb{E}$ 为所求,$\mathbb{E}(i)$ 为在已经取出 $i-1$ 个数字时,取到第 $i$ 个数字的期望次数。根据之前整理过的内容,“发生概率为 $p$ 的事件,在期望 $\dfrac{1}{p}$ 次之后会发生”,我们可以得到如下:

然后把他们加起来就是

思路是自然的。然后考虑本题,需要给每次操作附加一个权值。所以本质上我们可以分开计算,$g_i$表示已经取出 $i-1$ 个数字时,取到第 $i$ 个数字的期望步数,$ f_i$表示期望步数的cost

考虑如何计算 $f_i$。假设之前拿数进行了 $p$ 次操作,这一次拿 $i$ 需要 $q$ 次操作,那么这 $q$ 次操作的 $\rm \sum cost$ 就是

这个原理需要编一下。考虑前一半是之前拿数次数与当前拿数次数的乘积,可以知道此时的代价至少是这些;后一半在不考虑前面拿数的贡献后,可以考虑期望的意义,$q$ 既是期望次数,也是平均代价,所以可以知道当前的代价应该是 $q^2$ 。

然后就递推一下即可:

1
2
3
4
5
for (i = 1 ; i <= N ; ++ i){
n = 1.0 * N / (N - i + 1),
g[i] = g[i - 1] + n, f[i] = f[i - 1] + g[i] * n ;
}
printf("%.2f", f[N]) ;

*[SHOI2014]概率充电器

SHOI 概率充电器由 $n-1$ 条导线连通了 $n$ 个充电元件。进行充电时,每条导线是否可以导电以概率决定(每条边有一个通电概率),每一个充电元件自身是否直接进行充电也由概率决定(每个点也有一个通电概率)。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。

你突然想知道,进入充电状态的元件个数的期望是多少呢?

$1\leq n\leq 5\cdot 10^5$。

比较有难度的题目。

根据期望的线性性,可以知道这题只需要求出每个点被点亮的概率即可。考虑设 $f_u$ 表示 $u$ 的子树对 $u$ 的贡献,$g_u$ 表示 $u$ 真正的贡献。不难知道 $f_u\leq g_u$ 。

那么考虑分别求这两部分。首先常规树形 $dp$ 求出 $f_{root}=g_{root}$ 来,转移大概是考虑依次把子树合并进来:

然后考虑如何将贡献 $down$ 下去。那么考虑设 $h_u$ 表示只考虑祖先的贡献时,$u$ 亮的概率。不难知道 $g_u=f_u+h_u$ 。那么考虑 $h$ 怎么求。发现一般这种 down 形态的 dp 都要减去当前子树的贡献。所以对于 $h_v$ 而言,有如下转移:

考虑分子上是父亲传到儿子的概率,$h_v$ 是从父亲处导电的概率,那么可以知道如果想要父亲传到儿子,必须要使之互斥,即需要让 $h_v\times \Pr(\texttt{不通过儿子传到父亲})=\Pr(\texttt{父亲传到儿子})$ ,这是分母的来由。

考虑如果本身不能「不通过儿子传给父亲」,那么父亲的就不能传给儿子,此时 $h_v=0$,需要特判。

好绕啊好绕啊…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
il void dfs0(int u, int fa){
f[u][0] = base[u] ;
for (int k = head[u] ; k ; k = next(k)){
if (to(k) == fa) continue ;
dfs0(to(k), u), f[u][0] += (1 - f[u][0]) * val(k) * f[to(k)][0] ;
}
}
void dfs1(int u, int fa){
for (int k = head[u] ; k ; k = next(k)){
if (to(k) == fa) continue ;
double p = f[to(k)][0] * val(k) ;
if (fabs(1 - p) <= eps) {dfs1(to(k), u) ; continue ;}
double q = f[u][0] + f[u][1] - f[to(k)][0] * val(k) ;
f[to(k)][1] = (1 - f[to(k)][0]) * q / (1 - p) * val(k) ;
dfs1(to(k), u) ;
}
}
int main(){
cin >> N ;
double o ; int i, u, v, w ;
for (i = 1 ; i < N ; ++ i)
scanf("%d%d%d", &u, &v, &w), o = w * 0.01, add(u, v, o) ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &w), base[i] = w * 0.01 ;
dfs0(1, 0), dfs1(1, 0) ;
for (i = 1 ; i <= N ; ++ i)
ans += (f[i][0] + f[i][1]) ;
return !printf("%.6lf\n", ans) ;
}

转移时有后效性的题目

[HNOI2013]游走

一个无向连通图,顶点从 $1$ 编号到 $n$ ,边从 $1$ 编号到 $m$。

小Z在该图上进行随机游走,初始时小Z在 $1$ 号顶点,每一步小Z以相等的概率随机选择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z到达 $n$ 号顶点时游走结束,总分为所有获得的分数之和。

现在,请你对这 $m$ 条边进行编号,使得小Z获得的总分的期望值最小。

$n\leq 500,1\leq m\leq 1.2\times 10^5$ 。

首先可以贪心地知道期望走过次数越多的边,自然希望他编号越小。

考虑由点推边。即设 $f_i$ 表示 $i$ 这个点经过的次数。那么可以知道有

于是可以高斯消元求出每个 $f_i$ 。之后考虑一条边 $(u,v)$ 的期望经过次数就是

注意以上所有的操作都不包括 $n$ 号点,因为到 $n$ 号点就不会再走了。

CF24D Broken Robot

$n$ 行 $m$ 列的矩阵,一开始在点 $(x,y)$,每次等概率向左,右,下走或原地不动,但不能走出去,问走到最后一行期望的步数。

注意,$(1,1)$ 是木板的左上角,$(n,m)$ 是木板的右下角。

首先是倒推的思想,从 $(x,y)$ 走到最后一行状态的过程不好描述,可以转化为从最后一行走到 $(x,y)$ 。

考虑转移

发现具有后效性,于是考虑消元。个人认为至少有如下几档部分分:

40 pts $\max\{n,m\}\leq 25$

这个就可以把 $n \times m$ 个元素放在一起消元,复杂度是 $(n^3\cdot m^3)$ 的。

70 pts $\max\{n,m\}\leq 100$

发现每一行和其他行之间的关系只有 $f_{i+1,j}$ ,那么不难想到倒序枚举每一行,对这一行内的元素进行消元,此时 $f_{i+1}$ 的所有元素均已知。复杂度是 $O(n\cdot m^3)$ 的。

85 pts $\max\{n,m\}\leq 500$

发现对于要消元的矩阵,对于每一行只有 $i,i-1,i+1,n+1$ 四个列的位置是有元素的,所以每次对于一行而言,可以只进行 $O(1)$ 次消元。这样就是 $O(n\cdot m^2)$ 的了。

100 pts $\max\{n,m\}\leq 3000$

发现不止横向有性质,纵向同样有性质。发现对于每一列,至多会有 $3$ 个元素。这样纵向也是 $O(1)$ 的了。于是总复杂度 $O(n\cdot m)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
db ans[N] ;
db f[N][N] ;

void gauss(int n){
for (int i = 1 ; i <= n ; ++ i){
if (i < n) f[i][i + 1] /= f[i][i] ;
f[i][n + 1] /= f[i][i] ; f[i][i] = 1.0 ;
if (i < n) f[i + 1][i + 1] -= f[i + 1][i] * f[i][i + 1] ;
if (i < n) f[i + 1][n + 1] -= f[i + 1][i] * f[i][n + 1] ;
f[i + 1][i] = 0 ;
}
ans[n] = f[n][n + 1] ;
for (int i = n - 1 ; i >= 1 ; -- i)
ans[i] = f[i][n + 1], ans[i] -= ans[i + 1] * f[i][i + 1] ;
}

int n, m ;
int x, y ;

int main(){
cin >> n >> m >> x >> y ;
for (int i = n - 1 ; i >= x ; -- i){
for (int j = 1 ; j <= m ; ++ j){
if (j == 1 && j == m){
f[j][m + 1] = 1.0 + ans[j] * 1.0 / 2.0 ;
f[j][j] = 1.0 / 2.0 ;
}
else if (j == 1){
f[j][m + 1] = 1.0 + ans[j] * 1.0 / 3.0 ;
f[j][j] = 2.0 / 3.0, f[j][j + 1] = - 1.0 / 3.0 ;
}
else if (j == m){
f[j][m + 1] = 1.0 + ans[j] * 1.0 / 3.0 ;
f[j][j] = 2.0 / 3.0, f[j][j - 1] = - 1.0 / 3.0 ;
}
else {
f[j][j] = 3.0 / 4.0 ;
f[j][j - 1] = - 1.0 / 4.0 ;
f[j][j + 1] = - 1.0 / 4.0 ;
f[j][m + 1] = 1.0 + ans[j] * 1.0 / 4.0 ;
}
}
gauss(m) ; //debug(ans, 1, m) ;
for (int j = 1 ; j <= m ; ++ j)
f[j][j] = f[j][j - 1] = f[j][j + 1] = f[j][m + 1] = 0 ;
}
printf("%.8lf\n", ans[y]) ; return 0 ;
}

[HNOI2011]XOR和路径

给定一个无向连通图,其节点编号为 $1$ 到 $N$,其边的权值为非负整数。试求出一条从 $1$ 号节点到 $N$ 号节点的路径,使得该路径上经过的边的权值的 “XOR和”最大。该路径可以重复经过某些节点或边,当一条边在路径中出现多次时,其权值在计算“XOR 和”时也要被重复计算相应多的次数。

直接求解上述问题比较困难,于是你决定使用非完美算法。具体来说,从 $1$ 号节点开始,以相等的概率,随机选择与当前节点相关联的某条边,并沿这条边走到下一个节点,重复这个过程,直到走到 $N$ 号节点为止,便得到一条从 $1$ 号节点到 $N$ 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。

$2≤N≤100,1\leq M≤10000$ 。

那必然是要先猜一波期望对xor运算也具有线性性,但实际上并没有。

感觉可能是需要记住的一个 $trick$ ,位运算时位与位之间是独立的,所以可以分别对每一位计算。那么对每一位计算就可以直接按 $0/1$ 分类讨论来转移。

具体的,还是考虑倒推。个人感觉这是因为最初的决策可能延伸出许多不同的决策,导致很难对这个过程进行统计。但是如果倒推的话,就相当于从一个已知结果出发走向另一端的已知开始。所以会相对容易一点?

于是考虑设状态 $f_x$ 表示当前二进制位下, 从 $x$ 走到 $n$ 这一位的期望,也就可以等价于这一位为 $1$ 的概率。于是有转移

然后就可以消元了,复杂度 $O(n^3\log V)$ 。注意自环只统计一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int maxv ;
int n, m ;
int deg[N] ;

db res ;
db ans[N] ;
db f[N][N] ;

void gauss(int L){
for (int i = 1 ; i <= L ; ++ i){
int r = i ; db t ;
for (int j = i + 1 ; j <= L ; ++ j)
if (f[r][i] < f[j][i]) swap(f[r], f[j]) ;
for (int j = L + 1 ; j >= i ; -- j) f[r][j] /= f[r][i] ;
for (int j = i + 1 ; j <= L ; ++ j)
for (int k = L + 1 ; k >= i ; -- k)
f[j][k] -= f[j][i] * f[r][k] ;
}
ans[L] = f[L][L + 1] ;
for (int i = L - 1 ; i >= 1 ; -- i){
ans[i] = f[i][L + 1] ;
for (int j = i + 1 ; j <= L ; ++ j)
ans[i] -= ans[j] * f[i][j] ;
}
}

int main(){
cin >> n >> m ; int u, v, w ;
for (int i = 1 ; i <= m ; ++ i){
u = qr(), v = qr() ;
w = qr() ; chkmax(maxv, w) ;
add_e(u, v, w) ; if (u != v) add_e(v, u, w) ;
}
// debug(deg, 1, n) ; cout << cnt << '\n' ;
for (int v = 1 ; v <= maxv ; v <<= 1){
for (int i = 1 ; i <= n + 1 ; ++ i)
for (int j = 1 ; j <= n + 1 ; ++ j)
f[i][j] = 0.0 ;
for (int i = 1 ; i < n ; ++ i){
f[i][i] = deg[i] ; int xs = 0 ;
for (int k = head[i] ; k ; k = next(k)){
if (!(val(k) & v)) f[i][to(k)] -= 1.0 ;
else f[i][to(k)] += 1.0, xs += 1 ;
}
f[i][n + 1] = 1.0 * xs ;
}
f[n][n] = 1.0 ;
/*
for (int i = 1 ; i <= n + 1 ; ++ i)
for (int j = 1 ; j <= n + 1 ; ++ j)
cout << f[i][j] << " \n"[j == n + 1] ;
*/
gauss(n) ; res += ans[1] * v ;
}
printf("%.3lf\n", res) ; return 0 ;
}