期望

好像没有什么知识点呀 😅

满足可加性 $E(ax+by)=aE(x)+bE(y)$

当事件 $x,y$ 相互独立时满足可乘行 $E(x\times y)=E(x)\times E(y)$

$n$ 个相互独立取值在 $[0,1]$ 的随机变量，其中第 $k$ 小的随机变量的值的期望

考虑引入一个新随机变量 $n+1$ ，发现第 $k$ 小的随机变量的值期望等于新点在第 $k$ 小变量前面的概率

因为是连续随机变量，分布是均匀的，所以可以抽象成排列来考虑，将随机变量看成隔板，现在隔板将 $[0,1]$ 均匀分成 $n+1$ 份，而 $k$ 前面有 $k$ 份，所以第 $k$ 小的随机变量的值的期望是 $\frac{k}{n+1}$

典其实下面也有好多典题 😅

P4316 绿豆蛙的归宿

题意：求 $dag$ 上从 $S$ 走到 $T$ 的期望步数

倒推：设 $f_u$ 表示从 $u$ 走到 $T$ 的期望步数，转移是 $f_u=\sum\limits_{v}^{(u,v) \in E} \frac{(f_v+w)}{deg_u}$ 其中 $deg$ 是出度

正推：设 $f_u$ 表示从 $S$ 走到 $u$ 的期望步数，转移是 $f_v=\sum\limits_{u}^{(u,v) \in E} \frac{(f_u+g_u \times w)}{deg_u},g_u=\sum\limits_{u}^{(u,v) \in E} \frac{g_u}{deg_u}$

倒着推很没意思，但是正着推感觉好怪，但是仔细想想是对的，因为我不一定走 $(u,v)$ 这条边，等于就是 $E(a+bx)$ 中的 $x$ ，但是为啥倒推是对的呀 🤔，因为从 $u$ 出发必定要走一条出边，所以概率和为一，也就是 $x=\frac{w}{deg}$ 了

正推：code

我不会做部分

CF235B Let’s Play Osu!

二次期望

我们现在想求 $E(x^2)$ 不会，嘿嘿 🤭

假设现在连续 $O$ 长度为 $x$ ，我们加上一个 $O$ 的贡献是 $E((x+1)^2)-E(x^2)=E(x^2)+E(1)+E(2x)-E(x^2)=E(2x+1)$

现在我们需要知道 $E(x)$ ，容易发现 $E(x)=(E(x-1)+1)\times p_i$

P1654 OSU!

和上面差不多

P1850 [NOIP2016 提高组] 换教室

设 $f_{i,j,0/1}$ 表示我现在上到第 $i$ 节课，用了 $j$ 次换教室机会，现在在 $c_i/d_i$ 的期望步数，直接 $dp$ 即可

~~代码我已经看不懂了~~

P2473 [SCOI2008] 奖励关

🕊🕊🕊

P6835 [Cnoi2020]线形生物

简单题 💧💧💧

不想写了看题解去吧

P4206 [NOI2005] 聪聪与可可

🕊🕊🕊

CF280C Game on Tree

考虑 $dp$ ，发现根本不会做🤡

那就把每个点根据期望的线性性拆开

设现在的点是 $u$ ， $u$ 有 $x$ 个祖先，将操作看成序列，发现 $u$ 会有贡献当且仅当所有祖先都在我后面，所以期望贡献是 $\frac{1}{dep_u}$ ，这玩意我想了一年 👈🤣

#2544. 「JXOI2018」游戏

🧐🧐🧐

感觉和上面的很像，只用检查所有区间内没有约数的数就可以了

然后这个题还有一个好玩的东西

现在有 $n$ 个球，求随便选出 $k$ 个关键球，最后一个点位置的期望

我现在要算最后一个关键球位置等于 $n-\text{球在所有关键球后面的个数}$

先不考虑球的标号，假设现在已经选出所有关键球，现在就等于有 $k+1$ 个抽屉，等概率放球，所以在所有关键球后面的概率是 $\frac{1}{k+1}$ ，那么在所有关键球后面球的期望是 $\frac{n-k}{k+1}$ ，那么最后一个关键球位置期望就是 $n-\frac{n-k}{k+1}=\frac{(n+1)k}{k+1}$

所以答案乘上 $n!$ 就对了

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

有一半的分是 $k=n$ 😍

首先先想一个贪心看看怎么做

从后往前考虑，如果他的倍数有奇数个要操作那么就为 $1$ ，否则为 $0$

不难发现一定是优的

想到这个 $100$ 分就很简单了

设 $f_i$ 表示还需要操作 $i$ 个灯，这时我想减去一个灯的期望次数，转移方程显然 $f_i=1+(n-i)\times(f_{i+1}+f_i)$ ，就是如果我这次操作没有成功会多一个灯需要操作，然后从 $i+1$ 个操作到 $i-1$ ，然后化简一下柿子就好了

P4284 [SHOI2014] 概率充电器

不会做👈🤣

首先发现期望根本没用，求概率就可以了。

思考一个点怎么着会被充上电，一种是自己直接充上，还有就是从上面充上电或者从下面充上电

发现是一颗树，所以从下面充上电很好做，自己直接冲上也是很简单的，现在就考虑怎么算从上面来的就好了

假设我现在在点 $u$ 并且已经算好了，我现在要贡献到子节点 $v$ 这一个操作，现在我对 $v$ 的贡献是这个点充上电的概率 $-$ 只从 $v$ 上来 $u$ 充上电的概率，然后就推一下柿子

设 $(u,v)$ 出现概率为 $A$ ， $v$ 充上电概率为 $B$ ， $x$ 为不算 $v$ 的充电概率， $y$ 为算 $v$ 的充电概率

有柿子：

$y=(1-x)AB+x$

$y=AB+x-xAB$

$y=AB+x(1-AB)$

$x=\frac{y-AB}{1-AB}$

$y-x=y-\frac{y-AB}{1-AB}$

乘上点系数就做完了

P3239 [HNOI2015]亚瑟王

我就是亚瑟王！😎😎😎

一开始我设的是 $f_{i,j}$ 表示考虑在第 $j$ 轮，我现在考虑到了第 $i$ 个并且选他的概率，但是不对 😔

正确的是设 $f_{i,j}$ 表示 $r$ 轮一块考虑，现在考虑到第 $i$ 个数，有 $j$ 轮已经选数的方案数

那么我不选数的概率是 $(1-p_i)^{m-j}$ ，选的就是 $1-(1-p_i)^{m-j}$

但是好像不会统计答案，发现我转移时的东西就是选的概率，所以在转移的时候统计就可以了

pjudge 21743 青鱼和怪兽

🐟🐟🐟

设 $f_{i,j}$ 表示玩家还有 $i$ 点血量，👾还有 $j$ 点血量时获胜的期望时间

转移方程： $f_{i,j}=\min(f_{n,m},1+p\times f_{i,j-1}+(1-p)\times f_{i-1,j})$

发现这有个取 $\min$ ，根本不会做，我也不能实数枚举 😔，但是发现每次都是对一个数和 $f_{n,m}$ 取 $\min$ ，仔细思考 🤔 发现 $f_{n,m}$ 是具有单调性的，可以二分 🤩🤩🤩

具体来说，假设现在二分的 $f_{n,m}$ 是 $x$ ，如果按 $x$ 算出来的 $f_{n,m}$ 比 $x$ 小说明你 $x$ 设大了，缩小，否则增大

#6513. 「雅礼集训 2018 Day10」足球大战

⚽⚽⚽

发现这玩意能直接算

主队在 $n$ 秒内进 $m$ 个球的概率是 ${n\choose m}\times p^m\times (1-p)^{n-m}$ ，客队换成 $q$ 就行了

现在想主队赢，那么概率就是 $\sum\limits_{i=1}^{n}({n\choose i}\times p^i\times (1-p)^{n-i}\times (\sum\limits_{j=0}^{i-1}{n\choose j}\times q^j\times (1-q)^{n-j}))$

枚举主队进球数，对客队进球数那个 $\sum$ 做一个前缀和就好了

注意 $n$ 是 $1e7$ 级别的，不能快速幂，要预处理次方

#6495. 「雅礼集训 2018 Day1」树

~~倒悬的splay~~ （有端暗示

有一个经典技巧，发现不会期望，可以将答案按某些性质划分为一些类，然后对于每类计数

设 $f_{i,j}$ 表示现在树上有 $i$ 个点，最大深度为 $j$ 的方案数，考虑现在加入第 $i+1$ 个点怎么做

然后不会做👈🤣

🤔 一下发现好像就是不能转移，但是发现根节点性质很好，所以考虑加入的是根节点

发现 $2$ 号节点一定是连向 $1$ 号节点的，所以按这玩意分类

没有子节点：这就是初始化的值

有子节点：枚举 $2$ 号节点子树大小以及深度，然后枚举剩下的子树加上根节点组成的树的节点数和深度，拼一块就好了

注意转移顺序

~~所以这玩意是 $O(n^4)$ 的~~

CF1187F Expected Square Beauty

推柿子

首先求一下 $E(B(x))$ ，这玩意非常简单，就等于 $1+\sum\limits_{i=2}^{n}[x_{i-1}\not=x_i]$

然后平方一下： $E(B(x)^2)=E((1+\sum\limits_{i=2}^{n}[x_{i-1}\not=x_i])\times (1+\sum\limits_{i=2}^{n}[x_{i-1}\not=x_i]))$

化简：

$E(B(x)^2)=E(1+2\sum\limits_{i=2}^{n}[x_{i-1}\not=x_i]+\sum\limits_{i=2}^{n}[x_{i-1}\not=x_i]\sum\limits_{j=2}^{n}[x_{j-1}\not=x_j]$

发现第 $i$ 个 $[x_i\not=x_{i-1}]$ 之和第 $i-1,i,i+1$ 有关，把这些拿出来单独做，剩下的直接乘就好了

[AGC006C] Rabbit Exercise

~~这个性质我在初三考 NOIP 的时候场上想出来了，但是高一做这道题的时候没想出来 👈🤣~~

第 $i$ 只兔子跳完位置的期望是 $\frac{2\times a_{i-1}-a_i+2\times a_{i+1}-a_i}{2}=a_{i+1}+a_{i-1}$

这玩意不就是 $NOIP2021$ 方差嘛！那就差分一下，然后现在第 $i$ 只兔子跳等于 $swap(a_i,a_{i+1})$

然后这个万一就可以倍增了/hanx

#2325. 「清华集训 2017」小 Y 和恐怖的奴隶主

首先先列出 $dp$ ： $f_{i,a,b,c}$ 表示进行了 $i$ 轮，有 $a$ 个 $1$ 滴血的👾，有 $b$ 个 $2$ 滴血的👾，有 $c$ 个 $3$ 滴血的👾的期望，转移很简单，但是有点长，不想写了开摆，答案就是打怪兽时转移转移的概率

每一层的转移都是一样的，并且发现状态数不是很多，考虑用矩阵优化 $dp$ ，现在时间复杂度是 $Tstate^3\log n$ 这个有点大，过不去，但是因为矩阵乘向量是 $O(n^2)$ ，可以预处理出所有 $2^i$ 的矩阵，直接拼起来求答案，时间复杂度 $O(state^3\log n+Tstate^2\log n)$

实测 $state$ 大小是 $165$ ，加上一个答案就是 $166$

gym102978 H. Harsh Comments

CF643E Bear and Destroying Subtrees

无语了 👈🤣

首先考虑 $O(n^2)$ 的 $dp$ 怎么做

设 $f_{u,j}$ 表示以节点 $u$ 为根节点，树深度为 $j$ 的概率，但是发现这样转移要搞一个前缀和，不如直接把状态改为：以节点 $u$ 为根节点，树深度小于等于 $j$ 的概率，转移就很简单了 $f_{u,j}=\prod\limits_{v}^{(u,v)\in E} (\frac{f_{v,j-1}}{2}+\frac{1}{2})$