概率与期望题目总结
No0Chenquanlin
·
2024-02-05 10:01:10
·
个人记录
概率与期望18题联合题解 Part_1:简单期望
这部分期望题目较为简单基础，是期望的练手题，思维难度较小。
T1
基础期望dp 。依照定义：期望= 概率\times 贡献做即可。
本题提醒我们：在正向转移发现无法解决，且这些选择都具有多个，难以枚举，因而概率相同 时，要考虑逆向 dp 。
事实上，绝大部分的概率dp 都是逆向的。逆向dp 的实现可以考虑dfs .
代码：Link
T2
本题提醒我们：在遇到高次项的期望贡献时要拆开来看，分别计算一次项对应的贡献。
代码：Link
T3
简单推个小式子即可。能蒙对当且仅当相邻的两题答案一样，相邻两题答案的组合共有a[i]\times a[i-1] 种情况，蒙对有min(a[i],a[i-1]) 种情况，相除就是单个题目的期望，加和得到总期望。
代码:Link
本题提醒我们：期望是线性的 ，我们可以通过计算每一个样本的期望得到集合里总的期望。
T4
简单题。状态一眼就能设出来，然后依据概率转移即可。
本题提醒我们：当选择的个数是有限、可枚举的且通常概率不尽相同 时，我们可以通过枚举每一种情况来正向 进行期望dp 。
Link
T6
简单题。仍然运用期望的线性性质，算出每个格子的期望，小小容斥一下再相加即可。
本题提醒我们：？？？好像也没什么。就是注意算概率的时候要不重不漏，有时需要容斥等细微处理，以及卡精度问题。
代码：Link
T7
和T2差不多，注意同时要计算len 的期望。
代码：Link
Part_2:进阶期望
这部分期望题目难度逐渐上升，是期望的进阶题，具有思维难度，同时还会结合组合、图论等其它知识点，大部分是远古时期省选题目。
T5
思维题。还是先考虑拆总的期望为每个人的期望，再列出式子即可。
后面的方法就很多了，可以暴力拆式子化简，也可以用long double存组合数硬算概率。具体见两篇题解。
代码在题解里，就不放了。
T8
显然操作顺序与最终答案无关，因此我们可以先将操作装进结构体排序，将所有包包放在前面，碎片放在后面。因为所有的挑战只有成功/失败两种结果且每种结果概率不等，因此显然是正向dp 。容易想到定义dp[i][j][k] 为当前在第i 个挑战，一共赢了j 场，目前背包有k 空间的概率，于是分类讨论赢/输的情况，那分类讨论一下是包包还是碎片，分别转移即可。
本题提醒我们：正向dp 的判定，dp 设上题目所有的维度，但绝不要设胜负（成功与否） ，因为这是期望里的一部分！！！
Link
T9
由于在每个节点有多个等概率的选择，因此显然倒序dp 。我们可以预处理两点之间距离dis[i][j] 和猫猫在位置i ，老鼠在位置j 的情况nxt[i][j] 表示猫猫会走到哪里，然后用记搜实现倒序dp ，令猫和老鼠的位置分别是x,y ，老鼠下一步可能在z ，则式子显然:dp[x][y]+=dfs((nxt[x][y], z)+1)/(deg[y]) ，所求即为dfs(s,t) 。
本题提醒我们：几乎所有图上期望都是倒序dp ，且一般多用记搜实现。
代码：Link
T10
期望好题。
先判断是正序还是倒序 dp 。
庄家每次可以等概率选取一张牌，有多个等概率的选择，因此是倒序dp 。
现在考虑状态怎么设。既然是倒序dp ，那就要从最终状态反推回原状态。最后的状态是只有一个人在游戏中，那这个人的胜率就是1 ，且这个人是庄家。于是我们考虑设dp[i][j] 表示目前游戏中有i 人，从庄家开始数第j 个人的胜率，于是初始状态就可以表示为dp[1][1]=1 ，所求即为dp[n][i](1\le i \le n) 。有了状态，式子就很好得到了：我们枚举每一张卡片k_i ，得到从庄家开始数第d_i 个人会死，那么对于每一张卡片所确定出的庄家d_i+1 ，我们可以求出来当前的人j 在该庄家下的排名w_i ，这是好求的，然后就dp[i][j]+=dp[i-1][w_i]/m 转移即可。
这道题的难点是设状态。我们之所以这样设，是因为发现了以下两点：
在设计第二维时，考虑到每一个人在本质上没有区别 ，有区别的只是庄家这个身份 ，因此不能简单地按照编号定义每个人，而是要转换思路，以庄家为基准 定义每一个人。
在设计第一维时，如果简单地将轮次 作为第一维，那么在倒序枚举的情况下无法确定初始状态 ，不得不改变一下方式。我们知道初始状态应当是只剩一个庄家 ，根据刚才对第二维的设计对应的是就是庄家开始的第一个人 。第一维应当与时间（轮次）相对应，能随他们而变化的，只有剩余人数 这一维度。 因此得到了方程定义和初始状态：dp[1][1]=1 。
本题提醒我们：难一些的期望dp 的关键是设状态 。一般地，我们先确定dp 顺序 ，再确定如何表示初始状态 ，依照这两点来定义dp 方程。
代码：Link
出了dp状态定义，方程式一般不会太难。
T11
先回顾上文写的那句话。
然后——
"[NOIP2016]换教室"默默地向你翻了一个白眼。先分析dp 顺序，由于只有成功/失败两种情况 且概率各不相同 ，显然正序dp 。
有了顺序，状态就好设了。设dp[i][j][0/1] 表示第i 个时间段，liuliu 一共申请了j 门课，当前这一门课申请(1) ，未申请(0) 的期望。
千万不要设胜负！！！
转移也非常简单。显然 dp[i][j][0/1] 会由 dp[i-1][j][0/1] 或 dp[i-1][j-1][0/1] 转移而来，由于n\le 300 ，可以Floyd 预处理出两点之间距离，分类讨论一下上一个时间段与当前时间段自己所在的位置，再与概率相乘即可。
本题提醒我们：分类讨论要看全，邻接矩阵存重边要判断边权，全源最短路之间最短路最好用Floyd 。
整体来看这道题还是进阶期望里挺简单的一道，几乎没有什么期望部分。
除了转移方程代码有点长。代码：Link
T12
设$dp[i][j]$表示第$i$轮后第$1→i-1$轮状态为$j$的期望，一般地，逆序枚举的期望$dp$初始状态就是$0$。令每个宝物额前提状态集合为$s[i]$，当前物品是$t$，那显然得到$dp$方程：
$if\ s[t]\ \&\ j\ ==0\ \ →dp[i][j]+=(max(dp[i+1][j],dp[i+1][j\ \&\ (1<<t)+p[t]])/n
else\ \ →\ dp[i][j]+=dp[i+1][j]/n
本题提醒我们：倒序dp 有多种方式 ：图论问题中 可以记搜（T1、T9）、可以倒序设状态（T10）、可以倒序枚举(T12)。
代码：Link
T13
假期望，真树形dp .
本题的前置：洛谷P3047。
该题的统计思想在本题中会用到，即up-down 的树形dp 思想。
在树形dp 维护信息时，很多时候我们需要O(n) 维护一个点到全局的信息，这时候就需要该思想。具体地，该思想通过的是两次dfs ，第一次的dfs 维护根节点向下的信息，第二次维护叶子节点向上到根节点的信息。但显然两次的信息会由重复，那么就需要容斥原理减去重复的一部分。
对于本题：
首次dfs 中，令父亲节点为x ，儿子节点为y ，通过边的概率为p ，由概率的计算公式P(A+B)=P(A)+P(B)-P(AB) ，则容易知道dp[x]=dp[x]+dp[y]\times p-dp[x]\times dp[y]\times p 。
第二次dfs 中，我们需要计算所有除去y 的子树内的点对y 处答案的贡献。那这个东西显然可以用x 来更新。但此时的dp[x] 已然包含了y 的子树的部分，因此需要减去。具体地，由公式P(A+B)=P(A)+P(B)-P(AB) ，此处的P(A+B) 就是dp[x] ，P(A) 是dp[y]\times p ，那么所求的P(B) 就是x 对y 作出的除y 子树以外的点的贡献。化简式子得到是\frac{dp[x]-dp[y]\times p}{1-dp[y]\times p} ，在根据概率公式计算即可。
注意当dp[y]\times p=1 时，该式子无意义，但同时意味着dp[y] 已然是1 ，直接跳过，向下遍历即可。
本题提醒我们：概率计算不重不漏 ，树形dp 要考虑二次遍历，上下转移 。
二次遍历，上下转移!! 代码：Link
T14
注意到是一个有环无向图，无法进行一般的树形转移。
由于点数较少，而边数过多，因此考虑转化边的期望为点的期望。设连接一边t 的两点x,y 的期望分别为p_x,p_y ，二者的度数分别为d_x,d_y ，那么这条边的期望q_t=\frac{p_x}{d_x}+\frac{p_y}{d_y} 。
考虑如何求点的期望。设点x,y 间有边相连，那么期望f_x=\frac{f_y}{d_y} 。由于点n 无从转移，因此一共有n-1 个这样的式子，未知数是f_i(1<i<n) ，考虑高斯消元解出期望。需要注意的是，点1 的初始期望为1 。
然后贪心，期望越大赋值越小即可。
本题提醒我们：图论中的期望可以化边为点 ，当未知数的转移不具有规律性，不可简单dp 时，要高斯消元来解。
T15
与上一道题有相似的地方，但也有不同。
求异或时，显然异或的每一位是互不相关的，因此我们可以分类讨论，求出每一位的期望。
显然这类图论题目都是倒序dp 。因此想到设f[i] 为i→n 的该位异或路径为1 时的概率。这里设的时候不能简单设路径的期望，因为只有异或值为1 才会对答案做出贡献。
式子就容易得出：
dp[x]=\frac{dp[y]}{deg[x]}(w(x,y)==0)+\frac{1-dp[y]}{deg[x]}(w(x,y)==1)
略微变形一下，高斯消元log\_MAX 次即可（一般直接取30\ or\ 31 ）。
期望dp ，初始状态为0 ，所求即为dp[1] 。
本题提醒我们：遇到异或这种运算时可以按位处理 ，设状态的时候要能直接表示出初始状态，由于一个点的异或值可能性有两种 ，且概率相加为1 （这很重要！到一个点的异或值的样本空间 只有0 和1 ），不然就要像T11一样表示两种情况(期望没有规律啊)！
代码：Link
T16
先考虑最优解 是什么：
显然每一次最右边的亮灯是必须要按的（没得选）。于是最优策略就是从大到小 枚举每一个亮灯，改变它左边灯的状态。这里O(n\sqrt n) 或O(nlogn) 都不难做到。
先分析dp 顺序。每个灯有多种可能的状态，因此倒序dp 。
状态怎么设？这是本题最难的地方。
分析题目给的可能的初始条件。在剩余最优策略还有k 步时，直接按最优策略走。
这道题应该算一道特殊性质题，因为没有这个k 步的条件，题目照样可以做，但状态会难设很多。原因是它提醒了我们每一次按灯有按正确和按错误 的两种可能性 ，设状态时可以从按灯正确与否 入手。
但是按灯的过程的阶段性 不强。上面的题目，一般都有轮数/时间段等限制，可以作为阶段 ，但是按正确与否的灯，似乎没有这方面的限制。
dp状态的设计，往往取决于转移时变化了什么。 按一次正确的灯，正确的灯会增加一盏，因此本题变化的是正确的灯的数量 ！！
我们不能简单的按了i 盏正确的灯时的期望，这样错误的灯的个数会影响答案统计。因此，设dp[i] 为从有i 盏灯需要按到i-1 盏需要按的期望，这样设隐含着本次按的灯是对的 这一条件，就好转移了。
方程是容易的：dp[i]=\frac{i}{n}+\frac{n-i}{n}\times(dp[i]+dp[i+1]+1) 。
含义是按对的概率(\times 1) + 按错的概率\times 按错所需的代价。
变形一下统计答案即可，细节见代码。
本题提醒我们：
要关注特殊性质
要关注转移过程中变化了什么，根据变化的量来设dp 状态。
代码：Link
Part_3:毒瘤期望
这部分期望题目，是期望题目中几乎不可做 的题，思维难度大。
T17
先讲40pts 的部分分，就是该题：
T17.1
两道题本质上是全等的，只有数据范围不同。
有多个模式串，自然想到AC 自动机。于是建出AC 自动机，对每一个字符串的末尾打上标记，所求就是最终停在每一个标记点的概率。
直接设每个点的概率是不好转移的，因为无法确定初始状态 。经过根节点的概率如何求出呢？是1 吗？但显然由于可以反复地返回根节点，因此这样是不成立的。
但是我们可以简单地求出经过每个点的期望。这部分是T14。求期望的原因是根据期望的定义，E(i)=P(i)\times 经过次数，但是本题中，到达终点就停下，这个次数是1 啊！因此求出的期望就是概率了。
那么高斯消元即可。由于一共最多可以建出 nm 个点，因此复杂度大致是O(n^3m^3) 的，可以通过该题。
本题提醒我们：多模字符串想到AC 自动机，注意概率和期望之间的灵活转化！
代码：Link
回到本题。O(n^3m^3) 的复杂度通过本题显然力不从心。考虑这个算法的冗余部分在哪里。高斯消元后我们求出了每一个自动机上的点的期望，但是所有非终点的期望我们实际上是不需要的 。于是考虑把所有非终点构成的集合的期望记作x_0 ，每一个终点的期望（即概率）记作x_{1 - n} 。
考虑到达每一个终点的过程。
发现一个显然的性质，每一个终点的到达，都是由一个无法匹配的串顺着预测匹配m 步得到的。因此x_i=\frac{x_0}{2^m} 。
但这样实际上是不正确的，不然所有的字符串概率应该相同。我们没有考虑在这个匹配路径上遇到其他字符串终点的情况。这样的情况发生意味着匹配字符串i 的某个前缀和干扰字符串j 的某个后缀完全重合 。在x_0 的基础上加上这个干扰匹配 的概率就是这条路径真正的概率了。
x_0+\sum_{j=1}^{n}dp[j]\sum_{k=1}^{n}\frac{1}{2^{m-k}}[pre_{i,k}=suf_{j,k}]
再结合一个显然的方程：\sum_{i=1}^{n}x_i=1 ，就可以高斯消元解n+1 个方程组了。
注意最终要一些奇怪的恒等变形？不然会奇奇怪怪地因为精度炸掉。
本题提醒我们：分析非完美算法失败的原因，考虑非完美算法的冗余在哪里，建立将所有不合法情况看成一种情况的意识 。
T18
在做了许多难度大的期望之后发现这道题也没有那么毒瘤了呢~~
显然的树形dp 。考虑两点之间路径的情况是从起点 x 到 lca 再到终点 y 的。由期望的线性性质 ，这两个部分我们可以分别计算 ，前缀和、差分 处理。于是考虑设 f[u] 为当前节点 u 到 fa[u] 的期望步数，反之 g[u] 为从 fa[u] 到 u 的期望次数。
注意求f 和g 的顺序是不可改变的！
原因是树形结构的特殊限制。从下到上的路径是唯一的 ，但从上到下的路径有着多种选择，依赖着从上到下的答案 。这本质上还是up-down 思想。
草稿本：那你为什么妄图先算g 忙了将近1h 啊然后式子就好列出了，注意分类讨论要细致。
f[u]=\frac{1}{deg[u]}+\sum_{x \in son[u]}\frac{1+f[x]+f[u]}{deg[u]}
这个表示的就是一步走对的可能+ 走错了，走到子节点，需要多一步返回的可能。
g[u]=\frac{1}{deg[fa[u]]}+\frac{1+g[u]+g[fa[u]]}{deg[fa[u]]}+\sum_{{x \in son[fa[u]]} \cap {x \ne u}}\frac{1+g[u]+f[x]}{deg[fa[u]]}
这个表示的就是一步走对的可能+ 走到自己父亲节点，需要一步返回的可能+ 走错儿子，需要一步返回的可能。
这个式子显然无法直接递推处理，因此需要化简一下，就成了：
f[u]={deg[u]+\sum f_x}\ \ \ \ g[u]=g[fa[u]+deg[fa[u]]+\sum f_x
递推处理就好了。注意初始化问题：f[1]=g[1]=0 以及dfs 中的部分细节问题。
本题提醒我们：树上问题大多转化为lca 问题，树形dp 中up-down 思想的贯彻导致统计答案的顺序很重要！
代码：Link
Part_4:写在最后
概率与期望的题单一共18 题，做到这里想必也是很不容易。最后总结一下关于概率与期望的几句话吧。
先 确定dp 顺序，是正序dp 还是倒序dp 。设状态很重要。一般地，好的状态能有好的初始状态和所求状态的表示 ，能够体现转移过程中变化的量 。
灵活结合其它算法解决问题。如一般图中用高斯消元，树上用up-down 思想的树形dp
勤思考，多写代码，培养强大的思维能力和代码能力，不要一味颓题解！
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Thats\ End.\ on\ 2024.2.17