Card Collector(期望+min-max容斥)
Card Collector(期望+min-max容斥)
woc居然在毫不知情的情况下写出一个min-max容斥
题意
买一包方便面有几率附赠一张卡，有(n)种卡，每种卡出现的概率是(p_i),保证(Sigma p_i le 1)，集齐所有种类卡牌期望买多少包方便面？
解法
看次题解前，你必须要理解当只有一种卡，他出现的概率是(p)，那么我期望购买$frac 1 p $包方便面就可以获得这种卡。
否则请你右上角，因为博主不会解释...
唯一的解释就是：
(期望购买包数)( imes)(每包里面出现一张的概率)=(张数)
所以把概率除过去就好了...
我们想把所有(frac 1 p)加起来，发现这样的错误的，原因是我们忽略了每次抽卡牌的时候可能抽到别的卡牌，把所有$frac 1 p $加起来相当于必须抽到一张卡牌后才能抽到另一张，这样是不对的。
但是这样启示我们可以容斥，根据一些显然的概率原理(如果你不承认就右上角)，出现(1)或者(2)号卡牌的概率是(p_1+p_2)。那么，(frac 1 {p_1+p_2})的意思是，我抽到一张(1)或者(2)的期望次数。那么，抽到一张(1)和一张(2)的期望次数就是
[1/p_1+1/p_2-1/(p_1+p_2)
]
为什么我们的期望里要减去(1/(p_1+p_2))，因为我抽(1)的时候可能抽出(2)，会省下一点期望，这个期望具体的值就是(1/(p_1+p_2))(看不懂就右上角)。
所以我们就可以愉快地容斥了
[E(A)=sum_{t subseteq U}(-1)^{|t|}(frac 1 {sum _{p in t}p})
]
实际上，这个式子就是(min-max)容斥。
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=25;
int num[maxn],n;
long double ans;
long double p[maxn];
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
num[1]=1;
for(register int t=2;t<maxn;++t)
num[t]=num[t-1]<<1;
while(~scanf("%ds",&n)){
for(register int t=1;t<=n;++t)
scanf("%Lf",&p[t]);
for(register int t=1,edd=1<<n;t<edd;++t){
long double delt=0;
register int cnt=0;
for(register int i=1;i<=n;++i)
if(t&num[i]){
delt+=p[i];
++cnt;
}
if(cnt&1) ans+=1.0/delt;
else ans-=1.0/delt;
}
printf("%.4Lf
",ans);
ans=0;
}
return 0;
}