Vjudge

原来似乎写过一种状压的做法，然后空间复杂度很不优秀。 今天来补一种神奇的方法。

给定集合SS，设max{S}max{S}为SS中的最大值，min{S}min{S}为集合SS中的最小值。 那么我们可以得到： max{S}=∑T⊆S(−1)|T|min{T}max{S}=∑T⊆S(−1)|T|min{T} 证明的话，大概就是如果你钦定一个最小值，并且它强制出现， 如果枚举所有子集，不难证明除了最大值之外，任何一个数的出现次数都是2k2k的形式。 并且子集大小的奇偶性一一对应。因此，除了最大值之外，任何一个值的贡献全部会互相抵消，最后剩下的值就只有最大值。

对于期望而言这样做也是正确的。

回到这道题目，我们max{S}max{S}表示集合中最晚出现的元素，minmin同理。 E(max{S})E(max{S})表示出现时间的期望。 那么我们要求的是E(max{E(max{全集})})，那么利用min−maxmin−max容斥，有： E(max{S})=∑T⊆S(−1)TE(min{T})E(max{S})=∑T⊆S(−1)TE(min{T}) 而E(min{T})=1∑i∈TpiE(min{T})=1∑i∈Tpi 那么枚举子集，直接dfsdfs实现就好了