zcmimi's blog

arrow_back概率共2篇文章

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-01-21 10:36:00
查看原题

点击跳转

设当前区间为[l,r]

res=\sum_{i=l}^r p_i\times[\prod_{j=l,j!=i}^r(1-p_j)]

s_{[l,r]}表示\prod_{i=l}^r(1-p_i)

res=s_{[l,r]}\sum_{i=l}^r \frac{p_i}{1-p_i}

a_i=1-p_i,b_i=\frac{p_i}{1-p_i}

res=\prod_{i=l}^ra_i\sum_{i=l}^rb_i

假设现在区间变成了[l,r+1]

A=\prod_{i=l}^ra_i,B=\sum_{i=l}^rb_i

res'=A\times a_{r+1}(B+b_{r+1})

=A(a_{r+1}B+a_{r+1}b_{r+1})

=A(a_{r+1}B+p_{r+1})

res'>res,那么a_{r+1}B+p_{r+1}>B

1-p_{r+1}+\frac{p_{r+1}}B>1

\therefore B<1

那么对于每个l,只需要找到最远的r使\sum_{i=l}^rb_i<1

而这又具有单调性,那么\mathcal{O(n)}就可以解决了

1/1
Search
search