hdu4336

Card Collector
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1717    Accepted Submission(s): 788
Special Judge

Problem Description
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.
 

Input
The first line of each test case contains one integer N (1 <= N <= 20), indicating the number of different cards you need the collect. The second line contains N numbers p1, p2, ..., pN, (p1 + p2 + ... + pN <= 1), indicating the possibility of each card to appear in a bag of snacks.

Note there is at most one card in a bag of snacks. And it is possible that there is nothing in the bag.
 

Output
Output one number for each test case, indicating the expected number of bags to buy to collect all the N different cards.

You will get accepted if the difference between your answer and the standard answer is no more that 10^-4.
 

Sample Input
1
0.1
2
0.1 0.4

Sample Output
10.000
10.500
題意就是收集卡片，直到收集到所有的卡片，算出收集卡片數的期望值。我這裡用的是容斥原理，也可以用狀態壓縮dp做，但是那個我還不會

這裡1.0/sum的意思我也說不清，網上很多解題報告說了用容斥原理卻沒說1.0/sum這個式子是怎麼得的，我感覺有點像高中那時候學的幾何分布算期望值的公式，幾何分布期望值時1.0/p，大家忘記了可以去查查。把幾個卡片的集合看成一個，那它的期望就是1.0/sum，不知道這樣理解不可以

#include<stdio.h>   
int main()  
{  
    double a[22],sum,temp;  
    int i,j,k,n;  
    while(scanf("%d",&n)!=EOF)  
    {  
        for(i=0;i<n;i++)  
            scanf("%lf",&a[i]);  
        sum=0;  
        for(i=1;i<(1<<n);i++)  
        {  
            j=0;  
            temp=0.0;  
            for(k=0;k<n;k++)  
            {  
                if(i&(1<<k))  
                {  
                    temp+=a[k];  
                    j++;  
                }  
            }  
            if(j&1)//奇加偶減   
                sum+=1.0/temp;  
            else sum-=1.0/temp;  
        }  
        printf("%.4lf\n",sum);  
    }  
    return 0;  
}  

#include<stdio.h>
int main()
{
	double a[22],sum,temp;
	int i,j,k,n;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
			scanf("%lf",&a[i]);
		sum=0;
		for(i=1;i<(1<<n);i++)
		{
			j=0;
			temp=0.0;
			for(k=0;k<n;k++)
			{
				if(i&(1<<k))
				{
					temp+=a[k];
					j++;
				}
			}
			if(j&1)//奇加偶減
				sum+=1.0/temp;
			else sum-=1.0/temp;
		}
		printf("%.4lf\n",sum);
	}
	return 0;
}