题目链接：

题目大意：

有n种卡片，每包中至多有一种卡片，概率分别为p1,p2,...pn,可能有的没有卡片，求包数的期望，使得每种卡片都有。

解题思路：

由于n最多只有20，可以进行状态压缩。

dp[i]表示在状态i获得的卡片的情况下，得到最后结果所需的包数期望。

则dp[i]=no*(dp[i]+1)+∑pp[j]*(dp[i]+1)+∑pp[k]*(dp[i|(1<<k)]+1).

no:表示没有卡片的概率，∑pp[j]表示第j种卡片已经存在，∑pp[k]表示第j种卡片当前还没有。显然no+∑pp[j]+∑pp[k]=1,所以花间得dp[i]=1+(no+∑pp[j])*dp[i]+∑pp[k]*dp[i|(1<<k)]

dp[1<<n-1]=0递推求出dp[0]即可。

代码：

#include 
    
     #include
     
      using namespace std;double dp[1<<20],pp[25];int main(){    int n;    while(~scanf("%d",&n))    {        double no=0;        for(int i=0;i
      
       =0;i--)        {            dp[i]=1;            double temp=0.0;            for(int j=0;j