arrow_back期望共17篇文章

概率

定义详见数学课本

条件概率

P(B|A)指A发生的前提下,B发生的可能性

P(B|A)=\dfrac{P(AB)}{P(A)}

乘法公式

P(B|A)P(A)=P(AB)=P(A|B)P(B)

全概率公式

设$\forall i

查看原题

点击加载点击跳转

设f(i,j,0),f(i,j,1)表示:

第i个时间段,已经用了j个机会,选择c_i与选择d_i(换/不换教室)的最小期望

设dis(i,j)表示i,j之间最短距离

转移方程:

f(i,j,0)=\min \begin{cases} f(i-1,j,0)+dis(c_{i-1},c_i)\\ \begin{aligned} f(i-1,j,1) &+dis(d_{i-1},c_i)\times k_{i-1}\\ &+dis(c_{i-1},c_i)\times(1-k_{i-1}) \end{aligned} \end{cases}

f(i,j,1)=\min \begin{cases} \begin{aligned} f(i-1,j-1,0) &+dis(c_{i-1},d_i)\times k_i\\ &+dis(c_{i-1},c_i)\times (1-k_i) \end{aligned}\\ \begin{aligned} f(i-1,j-1,1) &+dis(d_{i-1},d_i)\times k_{i-1}\times k_i\\ &+dis(c_{i-1},d_i)\times (1-k_{i-1})\times k_i\\ &+dis(d_{i-1},c_i)\times k_{i-1}\times (1-k_i)\\ &+dis(c_{i-1},c_i)\times (1-k_{i-1})\times (1-k_i)\\ \end{aligned} \end{cases}

查看原题

点击加载点击跳转

假设当前有了i个瓶盖,还差n-i个瓶盖

再买一个瓶盖在差的n-i个中的概率为\frac 1{n-i},

期望再买\dfrac n{n-i}次后拥有i+1个瓶盖

全部加起来就是\displaystyle \sum_{i=0}^{n-1} \frac n{n-i}

最终就是\displaystyle \left( \frac nn + \frac n{n-1}+\frac n{n-2}+\dots+\frac n1\right)

\frac xy+\frac ni=\frac {xi+yn}{yi}

查看原题

点击加载点击跳转

每个容器x求出它存活轮数的期望可以表示为

\sum_{i=1}^{n-1}P(x_i)

x_i表示第x个容器到第i轮仍未被击倒

记录L_i为i左边第一个比它大的数的位置,R_i为i右边第一个比它大的数的位置

每个容器i被击倒的时候也就是[L_i,i]或[i,R_i]的容器都被选中

设P(A)表示[L_i,i]全被选中,P(B)表示[i,R_i]全部被选中,l=i-L_i,r=R_i-i,

\displaystyle \begin{aligned} P(x_i) &=1-P(A)-P(B)+P(AB)\\ &=1-\frac{{n-1-l \choose i-l}-{n-1-r\choose i-r}+{n-1-l-r\choose i-l-r}}{n-1\choose i} \end{aligned}

查看原题

点击加载点击跳转

设f_i表示所有数\gcd为i还要加入的数的期望数量

ans=1+\frac{\sum_{i=1}^mf_i}m

可以知道f_1=0

f_i=1+\frac{\sum_{j=1}^m f_{\gcd(i,j)}}m(i>1)

继续推式子:

\begin{aligned} f_i &=1+\frac{\sum_{j=1}^m f_{\gcd(i,j)}}m\\ &=1+\frac{\sum_{d|i} f_d\sum_{j=1}^m [\gcd(i,j)=d]}m \end{aligned}

把分子拿出来

\begin{aligned} &\quad\sum_{d|i} f_d\sum_{j=1}^m [\gcd(i,j)=d]\\ &=\sum_{d|i} f_d\sum_{j=1}^{m/d} [\gcd(\frac id,j)=1]\\ &=\sum_{d|i} f_d\sum_{j=1}^{m/d} \sum_{x|\frac id,x|j}\mu(x)\\ &=\sum_{d|i} f_d \sum_{x|\frac id}\sum_{j=1}^{m/dx}\mu(x)\\ &=\sum_{d|i} f_d \sum_{x|\frac id}\mu(x)\left \lfloor \frac m{dx}\right\rfloor\\ \end{aligned}\\

设T=dx

=\sum_{T|i}\sum_{d|T} f_d \mu(\frac Td)\left \lfloor \frac mT\right\rfloor

带入原来的式子

f_i=1+\frac{\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)}m

设F_T=\sum_{d|T} f_d \mu(\frac Td)

当d\not = i时可以每算出一个f_i就更新所有F_x(i|x)

当d=i时没法直接更新,这时T=d=i,\mu(\frac Td)=\mu(1)=1

f_i=1+\frac{\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m+\frac{f_i\left\lfloor \frac mi \right\rfloor}m \\ f_i-\frac{f_i\left\lfloor \frac mi \right\rfloor}m=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m \\ f_i\frac{m-\left\lfloor\frac mi \right\rfloor}m=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m \\ f_i=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}{m-\left\lfloor\frac mi \right\rfloor}

这样就可以先算f_i,再算F_i了

[d\not=i]这个条件只在T=i的时候才有限制

枚举到T=i,计算f_i时,F_x(x<i)都已经计算好了

F_i还少了f[i] \times \mu(1)

这正好是要剪掉的部分

查看原题

点击加载点击跳转

可以先看一下LG P4868 Preprefix sum,很经典一道题,维护一下后缀和就可以了

这题的话就是把上面那道题变了一下

由于值域太大,我们可以使用 动态开点线段树 或 树状数组+离散化

查看原题

点击加载点击跳转

Favorite-Dice top: 0

我是没看题解和标签写出来的,完全不知道这是期望

假设你已经取了i个面,你取到没取过的一个面,概率是\frac {n-i}n

把所有概率加起来就是答案啦,也就是\sum_{i=0}^{n-1} \frac {n-i}n

查看原题

点击加载点击跳转

设E_x为x到n的期望时间

E_x = \sum_i E_i \times p_{xi}\prod_{j=1}^{i-1}(1-p_{xj})

我们可以用类似dij的思想来更新

每次取出E_x最小的x来更新

要注意我们现在求出来的还没算上1需要先停留在原地的概率,

除掉一个1-\prod p才是最终的期望

查看原题

点击加载点击跳转

当我们选中一个i后

i,i^2,i^3...,i^k都会被去掉

我们设d_t为可以去掉t的数字的个数

ans = \sum_{i=1}^n \frac 1 {d_i}

那么如何统计呢？

分解质因数

n = p_1^{k_1}p_2^{k_2}p_3^{k_3}p_4^{k_4}...

对于k_i贡献为1+\frac12+\frac12+\frac14+...