In your childhood, do you crazy for collecting the beautiful cards in the snacks? They said that, for example, if you collect all the 108 people in the famous novel Water Margin, you will win an amazing award.
As a smart boy, you notice that to win the award, you must buy much more snacks than it seems to be. To convince your friends not to waste money any more, you should find the expected number of snacks one should buy to collect a full suit of cards.
容斥原理
1 #include<stdio.h>
2 #include<string.h>
3 #include<algorithm>
4 #include<math.h>
5 using namespace std;
6
7 double p[25];
8
9 int main(){
10 int n;
11 while(scanf("%d",&n)!=EOF){
12 for(int i=1;i<=n;++i)scanf("%lf",&p[i]);
13 double ans=0;
14 for(int i=1;i<(1<<n);++i){
15 int bit=0;
16 double tmp=0;
17 for(int j=1;j<=n;++j){
18 if(i&(1<<(j-1))){
19 bit++;
20 tmp+=p[j];
21 }
22 }
23 if(bit%2)ans+=1.0/tmp;
24 else ans-=1.0/tmp;
25 }
26 printf("%.10lf
",ans);
27 }
28 return 0;
29 }