hdu 4366 Card Collector (容斥原理)

http://acm.hdu.edu.cn/showproblem.php?pid=4336

题意：有 n 张卡片 ，每张卡片出现的 概率 是 pi

每包至多有 一张卡片 ，也有可能没有 卡片 。

求  需要买多少包 才能集齐 n 张卡片  ，求包数的 期望 。

题解 ： 容斥原理 。

每个bag中什么卡的机会都有，说明每个概率都会有交集，这样就会想到一个图，就是右下面那个

然后就这个公式了，还是很好理解的

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<set>
 7 #include<map>
 8 #include<queue>
 9 #include<vector>
10 #include<string>
11 #define inf 0x7fffffff
12 #define maxn 60000
13 #define CL(a,b) memset(a,b,sizeof(a))
14 #define  ll  long long
15 using namespace std;
16 int n ;
17 double a[30] ;
18  int main()
19  {
20       int i  ;
21     while(scanf("%d",&n)!=EOF)
22     {
23         for(i = 0 ;i < n;i++)
24         {
25             scanf("%lf",&a[i]) ;
26         }
27         double sum = 0  ;
28        for(int msk = 1 ; msk < (1 << n);msk++)
29        {
30            double mul = 0 ;
31            int bits = 0 ;
32 
33            for(i = 0 ; i < n;i++)
34            {
35                  if(msk & (1 << i ))
36                 {
37                     bits ++ ;
38                     mul += a[i] ;
39 
40                 }
41            }
42 
43 
44                 if(bits & 1)
45                 {
46                     sum += 1.0/mul ;
47                 }
48                 else sum -= 1.0/mul ;
49 
50        }
51 
52        printf("%lf\n",sum) ;
53 
54     }
55 
56  }