几何分布
\[P(x=k)=(1-a)^{k-1}a,k>0
\]
容易发现，\(E(x)=\dfrac{1}{a}\)。
Min-Max 容斥
对于集合 \(S\)，有：
\[\max(S)=\sum_{T\subseteq S,T\neq \emptyset}\min(T)(-1)^{|T|+1}
\]
依据期望的线性性，有：
\[E(\max(S))=\sum_{T\subseteq S,T\neq \emptyset}E(\min(T))(-1)^{|T|+1}
\]
刚开始你有一个数字 \(0\)，每一秒钟你会随机选择一个 \([0,2^n-1]\) 的数字，与你手上的数字进行或（C++,C 的 |，pascal 的 or）操作。选择数字 \(i\) 的概率是 \(p_i\)。保证 \(0\leq p_i \leq 1\)，\(\sum p_i=1\) 。问期望多少秒后，你手上的数字变成 \(2^n-1\)。
定义 \(\min\) 为最先变为 \(1\) 的位变得时间，而 \(\max\) 则是最后。
考虑 \(\min-\max\) 容斥。把每个位看成一个变量，然后发现就是 \(\max(S)\)，每一位的最大值都是 \(1\)。
考虑 \(P(\min(T)=k)\)，发现就是至少一个 \(1\)，前 \(k-1\) 步没有选里面的任何一个位。而第 \(k\) 步则需要。
\[P(\min T=k)=(1-P(S\otimes T))P(S\otimes T)^{k-1}
\]
这是几何分布，是 \(1-P(S\otimes T)\) 的几何分布。
\[E(\min T)=\frac{1}{1-P(S\otimes T)}
\]
发现 \(O(3^n)\) 过不去。但是可以高维前缀和求 \(P(T)\)。
这里 \(P(T)\) 是一次操作能覆盖 \(T\) 的概率。