概率期望乱做

目录

• 写在前面
• Easy
• Medium
  • P1365、CF235B、P1654
  • CF280C
  • P4550
  • CF1042E
  • ICPC2024 online 2 - L
  • P6046
• Hard
• 写在最后

写在前面

唉唉数学大傻逼来写写典题。

题目来源：

• 【数学2-3】概率与统计
• xzy的概率期望题单
• vp
• Codeforces 标签筛选

Easy

• P1297：仅需考虑相邻位置的选项数量，即可计算每个位置的期望得分。
• P2111：设状态 \(f_{i, j}\) 表示考虑到前 \(i\) 道题，对了 \(j\) 道的概率，枚举每道题的情况转移即可。
• P6154：典中典之 DAG 随机游走求路径数量/长度的期望，直接倒着 DP 即可。
• P5104：第一个人抢钱期望显然即 \(\frac{2}{w}\)，剩余钱数的期望即 \(w-\frac{w}{2}=\frac{w}{2}\)，递推可知第 \(k\) 个人期望抢 \(\frac{w}{2^k}\)，抢完后期望剩余 \(\frac{w}{2^k}\)。
• SP1026：赠券收集问题，记 \(f_i\) 表示得到 \(i\) 个不同面时的期望次数，则再得到一个不同的面的单次概率为 \(\frac{n-i+1}{n}\)，显然是一个几何分布，则期望次数为 \(\frac{n}{n-i+1}\)，答案即 \(\sum_{1\le i\le n} \frac{n}{n-i+1}\)。
• CF148D：直接记搜。
• CF453A：记随机变量 \(X\) 为最终点数最大值，即求 \(\sum_{1\le i\le m} i\times P(X=i)\)，套路地转化：\(\sum_{i} P(X\ge i) = \sum_{i}1-P(X<i) = \sum_i 1 - \left(\frac{i-1}{m}\right)^n\)。

Medium

P1365、CF235B、P1654

典中典之 OSU 题。

对于 \(E(X)\) 很好维护直接加就行。

对于 \(E(X^2)\) 考虑拆贡献 \((X+1)^2 = X^2 + 2X + 1\)，则对于一长度为 \(X\) 的全 1 串，若贡献为 \(X^2\)，则长度每增加 1，\(X^2\) 就增加 \(2X + 1\)；则考虑期望的性质，可将期望拆为 \(E((X+1)^2)=E(X^2) + 2E(X) + 1\)，仅需考虑长度每增加 1 时，期望的增量 \(2E(X) + 1\) 即可。

考虑设 \(f_{i}\) 表示以 \(i\) 结尾的全 1 串，贡献为 \(X\) 时的期望贡献，则显然有 \(f_{i} = a_i\times (f_{i-1} + 1)\)；设 \(g_i\) 表示考虑前 \(i\) 个位置，全 1 串贡献为 \(X^2\) 时的期望贡献之和。则由上分析，每个位置的贡献为 \(a_i\times (2 f_{i} + 1)\)，则有：

\[g_{i} = \sum_{1\le j\le i} a_j\times (2f_{j} + 1) = g_{i - 1} + a_{i}\times (2f_{i} + 1) \]

对于 \(E(X^3)\) 仅需额外维护 \(f'_{i}\) 表示以 \(i\) 结尾的全 1 串，贡献为 \(X^2\) 时的期望贡献，再类似地再拆 \(X^3\) 即可。

CF280C

从组合角度考虑，问题即考虑构造若干对应删点顺序的排列，求排列长度的期望。发现每个节点在排列中出现，对长度的贡献均为 1，根据期望的线性性，考虑把每个点的贡献拆开，仅需考虑每个节点出现在排列中的概率即可。

发现一个点 \(i\) 被选中，当且仅当它的祖先都在它之后被选，考虑到根到该节点的链长为 \(\operatorname{dep}_i\)，则该点是这条链上第一个被选中的概率即 \(\frac{1}{\operatorname{dep}_i}\)。答案即：

\[\sum_{1\le i\le n}\frac{1}{\operatorname{dep}_i} \]

P4550

这题和 SP1026（见 Easy）的关系，和上面 OSU 三道题一样。

先拆贡献，若 \(k\) 次得到所有邮票，则总代价为 \(\sum_{1\le i\le k} i = \frac{k(k+1)}{2}\)，则 \(E(\sum_{1\le i\le k} i) = \frac{E(k^2) + E(k)}{2}\)。

求 \(E(k)\) 即 SP1026，对于 \(E(k^2)\) 同样考虑拆式子，若多获得一张新邮票的操作次数为 \(x\)，则有：

\[E((k + x)^2) = E(k^2) + 2E(x)E(k) + E(x^2) \]

由几何分布的知识有：

\[\begin{cases}E(x) = \frac{1}{p} = \frac{n}{n-i+1}\\E(x^2) = \frac{2 - p}{p^2} = 2E^2(x) - E(x) \end{cases}\]

记\(f_i\) 表示得到 \(i\) 个不同面时的期望次数，则分别考虑新出现一个面的贡献之和，有：

\[\begin{cases}f_i = \sum_{1\le j\le i} E(x)\\E(k) = f_n\\E(k^2) = \sum_{1\le i\le n} 2E(x)f_{i} + E(x^2) \end{cases} \]

答案即：

\[\frac{E(k^2) + E(k)}{2} \]

CF1042E

按权值升序排序后，考虑从第 \(i\) 个格子开始跳的期望步数，发现只能往权值更小（注意不能相等）的位置跳，贡献的增量即为 \(d = \sum (x_i - x)^2 + \sum (y_i - y)^2 = \sum (x_i^2 + y_i^2) - 2x_i\sum{x} - 2y_i\sum y + \sum(x^2 + y^2)\)。

发现两维分别考虑没有影响，于是分别维护权值更小的位置的数量 \(c\) 与 \(\sum x^2, \sum y^2, \sum x, \sum y\)，则很容易计算获得的贡献的期望增量 \(\frac{d}{c}\)，再考虑从权值更小的位置开始跳的期望步数之和的期望即可。

除了有点难调呃呃就是水题。

ICPC2024 online 2 - L

dztlb 大神秒了我看都没看，上去给大神写了个整数三分就过了。

显然两种操作不会交替使用，因为先进行操作 1 后进行操作 2，发现本次操作 1 实际上是没有贡献的。则一定是先不断进行操作 2 直至某个阈值 \(c\)，再不断进行操作 1 直至 0。

于是考虑枚举进行若干次操作 2 后的阈值 \(c\)，求得第一次操作使得小于该阈值的期望步数。一次操作的概率为 \(p = \frac{c}{t}\)，发现这是个典型的 \(r=1\) 的帕斯卡分布，仅需考虑不小于 \(k(k\ge 0)\) 次操作后使大于阈值的概率，考虑级数求和可知期望步数即：

\[p + p(1 - p) + p(1-p)^2 + \cdots = \frac{1}{p} = \frac{t}{c} \]

然后考虑操作 2 使得小于阈值后的取值在 \(0\sim c\) 中概率均等，则进行操作 1 的期望次数显然即：

\[\frac{1}{c+1}(0 + 1 + 2 + \cdots + c) = \frac{c-1}{2} \]

则对于某个阈值 \(c\) 的期望操作次数即为：

\[\frac{c-1}{2} + \frac{t}{c} \]

显然是个对勾函数的形式，可以直接解出或三分求得极值点。

P6046

妈的数据范围这么小

Hard

错误的 hard 根本做不出来。

写在最后