HDU 4336 Card Collector 容斥 数学期望 概率

题意：给出N个物品及每次获得第i个物品的概率 问获得所有物品的次数的期望、

从简单考虑 若只有一个物品  获得一个物品的期望是1/p （1/p * p = 1） 

这样可以推理得到 E1 = 1 / p1 , E2 = 1/ p2 , E12 = 1 / (p1+p2)  （即获得第一个物品或第二个物品的期望） 这样如果要计算获得第一个物品和第二个物品的期望 就要从E1和E2中减去重复的期望

 E(12) = E1 + E2 - E12  ，故可容斥

int n;
double p[25];

double solve() {
    double res = 0;
    for (int i = 1; i < (1 << n); i++) {
        int byte = 0;
        double sum = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                byte++;
                sum +=  p[j];
            }
        }
        //cout << sum << endl;
        if (byte % 2) res +=1 / sum;
        else res -= 1 / sum;
    }
    return res;
}



int main() {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) scanf("%lf", &p[i]);
        printf("%.5f\n", solve());
    }

}