hdu 4336 求概率状态压缩+容斥原理

傷城~ 2022-07-28 01:46 140阅读 0赞

# Card Collector #

**                                                                             Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
                                                                                                   Total Submission(s): 3667    Accepted Submission(s): 1817  
                                                                                                                                    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

Source

[2012 Multi-University Training Contest 4][]

题意: 有n个卡片,可以从零食中获得, 每一袋零食最多一张卡片, 可以没有卡片, 告诉你每张卡片出现的概率, 让你求能凑齐n张卡片的期望零食包数.

分析: 凑齐n张卡片, 也就是求各张卡片出现的期望包数的并集, 可以用容斥定理(A类B类元素个数总和= 属于A类元素个数+ 属于B类元素

个数—既是A类又是B类的元素个数。（A∪B = A+B - A∩B)

)来求.

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=100010,MOD=1e9+7;
    
    double a[23];
    
    void solve(int n)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf",&a[i]);
        }
        int all=1<<n;
        double ret=0;
        for(int i=1;i<all;i++)
        {
            int num=0;
            double p=0;
            for(int j=0;j<n;j++)
            {
                if(i&1<<j)
                {
                    num++;
                    p+=a[j];
                }
            }
            if(num & 1) ret += 1.0/p;
            else ret -= 1.0/p; //  1.0/p是算的包数
        }
        printf("%.6lf\n",ret);
    }
    
    int main()
    {
        int n;
        while(cin>>n)
        {
            solve(n); //求的是n个概率的交集,可以运用容斥原理
        }
        return 0;
    }

[2012 Multi-University Training Contest 4]: http://acm.hdu.edu.cn/search.php?field=problem&key=2012+Multi-University+Training+Contest+4&source=1&searchmode=source