概率学习（Genshin中）

标签：概率 数字 min max sum 学习 otimes Genshin

几何分布

\[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} \]

典 P3175 [HAOI2015] 按位或

刚开始你有一个数字 \(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\) 的概率。

标签：概率,数字,min,max,sum,学习,otimes,Genshin
From： https://www.cnblogs.com/british-union/p/17738902.html