zcmimi's blog

arrow_back期望共17篇文章

avatar
zcmimi
2020-09-09 18:14:00

概率

定义详见数学课本

条件概率

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

avatar
zc
2020-10-19 19:55:41

查看原题

点击跳转

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}

avatar
zc
2020-09-28 11:26:35

查看原题

点击跳转

假设当前有了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}

avatar
zc
2020-09-10 12:45:00
查看原题

点击跳转

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

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

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

记录L_ii左边第一个比它大的数的位置,R_ii右边第一个比它大的数的位置

每个容器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}

avatar
zc
2020-06-11 16:49:00
查看原题

点击跳转

f_i表示所有数\gcdi还要加入的数的期望数量

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)

这正好是要剪掉的部分

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

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

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

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

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

Easy top: 0

Solution:   期望题总是贼有意思。

  本题期望comboo的期望连续长度的平方,所以我们设f_i表示到了第i位的总期望combo,g_i表示到了第i位结尾的连续o的期望长度,那么分情况讨论:

  1. s_i == o
  2. s_i == x
  3. s_i ==\ ?
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

树形dp中的\text{up and down}

还有一点期望

设每个点能够通电的概率为P_i

那么ans = \sum_{i=1}^n P_i

我们先考虑up(只考虑子树))

分成两种情况:

  1. 直接通电 : q_i

  2. 被子节点通电 :

    (1-q_i) \times P_{to}(\text{子节点}) \times e_i.w(\text{连接的边导电的概率})

我们再考虑down(考虑子树外))

我们可以通过父节点的答案来更新子节点

父节点的答案是包括当前子节点的

可以把这部分除去然后按照up的方法更新

P_x= P_x' (1-P_x')*(P_{to}*e_i.w)(P_x'指根节点除去当前子节点的贡献的答案)

整理得: P_x'=\frac{P_x-(P_{to} \times e_i.w)}{1-(P_{to} \times e_i.w)}

(这里有个坑点:当1-(P_{to} \times e_i.w) = 0时这个式子就没有意义了)

\therefore P_{to} = P_{to} + (1-P_{to}) \times P_x' \times e_i.w

所以在下推的时候要特判一下

1/2
Search
search