标签：subset 题解 sum ABC331G mid Theta 式子

ABC331G

日常被bot吊打罢了。

首先注意到一件事是你 需要求一堆max的期望 对吧。所以其实上来就应该试试上 min-max容斥 的。但是鉴于我没有脑子，所以其实没想到也可以理解。

先来复习一下式子：

\[Emax(S) = \sum_{T \subset S} Emin(T)(-1)^{\mid T\mid - 1} \]

所以带入要求的东西就是

\[Elatest(S) = \sum_{T \subset S} Eearliest(T)(-1)^{\mid T\mid - 1} \]

\(Eearliest(T)\) 我们是会求的啊！它就等于

\[\frac{n}{\sum_{i \in T}c_i} \]

那么式子就是

\[Elatest(S) = \sum_{T \subset S} \frac{n}{\sum_{i \in T}c_i}(-1)^{\mid T\mid - 1} \]

现在式子只和 \(\sum_{i \in T}c_i\) 有关（还带一个容斥系数。）这就可以做背包了啊！暴力是 \(\Theta(nm)\) 的，可以用分治NTT优化到 \(\Theta(n \log ^2 n)\) ，或者付公主的背包一下做到 \(\Theta(n \log n)\) ，然后就没了。

啥都不会，只能罚坐！

标签：subset,题解,sum,ABC331G,mid,Theta,式子
From： https://www.cnblogs.com/miloHogwarts4ever/p/hui-bu-liao-yi-dian.html