hdu 4336 Card Collector 容斥原理 多校联合赛（四） 第六题
看了hdu上的题解之后了解 原来是容斥原理，顺便复习了一下
每个bag中什么卡的机会都有，说明每个概率都会有交集，这样就会想到一个图，就是右下面那个
然后就这哥公式了，还是很好理解的
下面是我的一个dfs
[cpp]
#include<iostream>
#include<cstdio>
using namespace std;
double s; int n,vis[25];
double a[25];
void dfs(int k,double sum,int cou,int j){
if(cou==k){
s+=1/sum;
return ;
}
for(int i=j;i<=n;i++){
sum+=a[i];
cou++;
dfs(k,sum,cou,i+1);
cou--;
sum-=a[i];
}
return ;
}
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++){
scanf("%lf",&a[i]);
}
double sum=0;
for(int i=1;i<=n;i++)
sum+=(1/a[i]);
for(int i=2;i<=n;i++){
s=0;
dfs(i,0,0,1);
if(i%2==0) sum+=(-1)*s;
else sum+=s;
} www.zzzyk.com
printf("%lf\n",sum);
}
}
作者：youngyangyang04
补充：软件开发 , C++ ,
