Qiuly

「HAOI2015」按位或 概率/期望+Min-Max容斥+集合幂卷积 loj2127
将位置拆开,其中对于二进制位下第 $k$ 个位置,设 $a_k$ 表示其变成 $1$ 所用的时间。设 $U$ 为全...
扫描右侧二维码阅读全文
27
2019/08

「HAOI2015」按位或 概率/期望+Min-Max容斥+集合幂卷积 loj2127

将位置拆开,其中对于二进制位下第 $k$ 个位置,设 $a_k$ 表示其变成 $1$ 所用的时间。设 $U$ 为全集,那么我们的答案就是 $E(\max(U))$ 。

考虑求出 $E(\min(U))$ 后通过 $\rm{Min-Max}$ 容斥的基本柿子求出 $E(\max(U))$ 即可。

设 $P(S)$ 为选中集合 $S$ 的概率,$P'(S)$ 为选中 $S$ 的子集的概率。那么 $\min(S)=k$ 的概率就是前 $k-1$ 次全部都是选中的 $S$ 的补集的子集,然后在第 $k$ 次不选所有的 $S$ 的补集的子集。

根据离散期望计算公式:$E(x)=\sum v\times P(v)$ ,我们可以得到:

$$ E(\min(S))=\sum_{k=1}^{\infty} k\times P'(S\oplus U)^{k-1}(1-P'(S\oplus U)) $$

将 $P'(S\oplus U)$ 简写为 $P$ ,那么柿子就会变成:

$$ E(\min(S))=\sum_{k=1}^{\infty} k\times P^{k-1}(1-P)\\ E(\min(S))=(1-P)\sum_{k=1}^{\infty} k\times P^{k-1} $$

设 $Sum=\sum_{k=1}^{\infty} k\times P^{k-1}$ :

$$ Sum=\sum_{k=1}^{\infty} k\times P^{k-1}\\ (1-P)Sum=\sum_{k=1}^{\infty} P^{k-1} $$

这个等于 $\frac{1-P^{\infty}}{i-P}$ ,然后就是 $0\leq P<1$ ,也就是说 $P^{\infty}=0$ ,直接忽略掉,剩下的就是 $\frac{1}{1-P}$ ,于是我们最终得到了:

$$ E(\min(S))=\frac{1}{1-P'(S\oplus U)} $$

所以接下来只需要考虑如何求 $P’$ 了,很显然我们可以得到转移柿:

$$ P’(S)=\sum_{T\subseteq S}P(T) $$

直接枚举的复杂度是 $O(3^n)$ 的,可以用集合幂卷积优化至 $O(2^nn^2)$ 。

代码还没写完 .

最后修改:2019 年 08 月 29 日 04 : 24 PM

发表评论