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)\) ，然后就没了。
啥都不会，只能罚坐！