关于期望线性性与min-max容斥

# 关于期望线性性与min-max容斥 # ——gym102978H Harsh Comments题解 ## 题目： 有 $n$ 个 $A$ 物品，价值为 $a_i$，$m$ 个 $B$ 物品，价值为 $b_i$。每次按价值加权等概率删掉一个物品（$val$/剩余$sum$），求删完 $A$ 物品的期望步数，对 $99824353 取模$。 $n,m,a_i\le100$。 ## 题解： 首先是min-max 容斥，将式子写为： $\sum_{S}(-1)^{|S|-1}\min_{i\in S}\{t_i\}$，**如果要使用min-max容斥，一定要考虑将其 $\min\{t_i\}$ 变为一个直接的表达式，否则一定做不出来**（就目前的题目来看）。 但如果直接做，我们发现由于不同的物品带有不同的权值，删除不同的物品会带来不同的后效性，考虑整个过程会非常麻烦。**所以直接考虑每个物品对 $S$的贡献**（这与以前先列出01变量在拆分不同，相反做困难题目的时候应该熟练考虑贡献而不是一步一步的列01变量）。 对于一个价值为 $val$ 的物品，其在 $S$ 之前被选择的概率为 :$\frac {val}{val+\sum_{i\in S}a_i}$。 于是对于 $a_i$，其贡献为，令 $sum=\sum_{i\in S}a_i$： $$ \begin{aligned} &\sum_{S}(-1)^{|S|-1}\sum_{i\in S}\frac{a_i}{sum+a_i}\\ =&\sum_{i}\sum_{sum}\frac{a_i}{sum+a_i}\sum_S[i\not\in S][sum_S=sum](-1)^{|S|-1}&&\color{red}{直接枚举元素！}\\ \end{aligned} $$ 后面这个相当于一个背包，可以解决。 $b_i$ 的贡献类似： $$ \sum_{i}\sum_{sum}\frac{b_i}{sum+b_i}\sum_S[sum_S=sum](-1)^{|S|-1} $$ 直接背包解决。