【HDU4336】Card Collector（Min-Max容斥）

【HDU4336】Card Collector（Min-Max容斥）

题面

Vjudge

题解

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

---

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

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

---

回到这道题目，我们(max{S})表示集合中最晚出现的元素，(min)同理。
(E(max{S}))表示出现时间的期望。
那么我们要求的是(E(max{)全集(}))，那么利用(min-max)容斥，有：
(E(max{S})=sum_{Tsubseteq S}(-1)^{|T|+1}E(min{T}))
而(E(min{T})=frac{1}{sum_{iin T}p_i})
那么枚举子集，直接(dfs)实现就好了

#include<cstdio>
int n;
double p[20],ans;
void dfs(int x,double e,int opt)
{
	if(x>=n){if(e>1e-7)ans+=opt/e;return;}
	dfs(x+1,e,opt);dfs(x+1,e+p[x],-opt);
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;++i)scanf("%lf",&p[i]);
		ans=0;dfs(0,0,-1);
		printf("%.6lf
",ans);
	}
}