题意：每包干脆面可能开出卡或者什么都没有，一共n种卡，每种卡每包爆率pi，问收齐n种卡的期望
思路：期望求解公式为：$E(x) = \sum_{i=1}^{k}pi * xi + (1 - \sum_{i = 1}^{k}pi) * [1 + E(x)]$，即能转换到x情况的期望+x情况原地踏步的期望。
因为n比较小，我们可以直接状压来表示dp[x]为x状态时集齐的期望。那么显然dp[111111111] = 0。然后我们状态反向求解。最终答案为dp[0]。
然后来看期望的求解：$E(x) = \sum_{i = 1}^{k}pi * [1 + E(xi)] + (1 - \sum_{i = 1}^{k}pi) * [1 + E(x)]$，E(xi)是E(x)某一位0变成1后的期望。
化简后：$E(x) = (\sum_{i = 1}^{k}pi * E(xi) + 1) / \sum_{i = 1}^{k}pi$
代码：
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 20 + 5;
const int M = maxn * 30;
const ull seed = 131;
const int INF = 0x3f3f3f3f;
const int MOD = 1e4 + 7;
double dp[1 << maxn];
double p[maxn];
int main(){
int n;
while(~scanf("%d", &n)){
// for(int i = 0; i < (1 << n); i++) dp[i] = 0;
for(int i = 0; i < n; i++){
scanf("%lf", &p[i]);
}
dp[(1 << n) - 1] = 0;
for(int i = (1 << n) - 2; i >= 0; i--){
double sump = 0, sumpe = 0;
for(int j = 0; j < n; j++){
if(!(i & (1 << j))){
sump += p[j];
sumpe += p[j] * dp[i | (1 << j)];
}
}
dp[i] = (sumpe + 1) / sump;
}
printf("%.6f\n", dp[0]);
}
return 0;
}