题目描述

小时候，谷学长买了很多干脆面，因为一旦集齐所有类型的卡片就有大奖可拿。
谷学长很聪明的意识到要想集齐全套卡片就得买相当多的干脆面，为了尽可能的省钱，他想计算出每种类型卡片均获得一张应买干脆面的期望数目。

输入

每个测试用例的第一行包含一个N(1 <= N <= 20), 表示干脆面里可能放置N种类型的卡片，第二行有N个数p1, p2, …, pN, (p1 + p2 + … + pN <= 1), 表示中到对应类型卡片的概率。
注意每袋干脆面最多只有一张卡片。

输出

对于每组测试用例，输出集齐N张不同类型的卡片所买干脆面的期望数目。结果保留三位有效数字。

样例输入

1
0.1
2
0.1 0.4

样例输出

10.000
10.500

思路

花了我很久很久的时间来解决这道题。。。

数学期望

在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。
需要注意的是，期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。期望值是该变量输出值的平均数。期望值并不一定包含于变量的输出值集合里。
大数定律规定，随着重复次数接近无穷大，数值的算术平均值几乎肯定地收敛于期望值。

性质

设C为一个常数，X和Y是两个随机变量。以下是数学期望的重要性质：[2]

  1. E(C) = C
  2. E(CX) = CE(X)
  3. E(X + Y) = E(X) + E(Y)
    4.当X和Y相互独立时， E(XY) = E(X)E(Y)
    性质3和性质4可以推到到任意有限个相互独立的随机变量之和或之积的情况。

参考资料

如何计算不等概率的抽卡次数期望？
为什么说A+B多算的这一块,是他?
为了集齐小浣熊干脆面108将卡,得吃多少袋干脆面？
假设小浣熊随机赠送的卡片共有 100 种（出现概率相同），那么集齐所有卡片所需购买小浣熊包数的数学期望是多少？
Coupon collector’s problem
干脆面大家都吃过，里头往往会有一张卡，一共几十种，集齐送奖品。假设只有三种卡，那么集齐卡片需要买的方便面包数X的期望是多少？如果是N种卡，期望又怎么算？
50个概率题
试题1—经典概率问题：优惠券收集问题
模拟要得到四张不同花色的牌所需要的选取次数，然后显示选中的四张牌（有可能一张牌被选了两次）。

结论

就是使用容斥原理即可，困难我很久的问题终于解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <iomanip>
using namespace std;

double Solve(int N, double p[])
{
    double ans = 0;
    for (int msk = 1; msk < (1 << N); msk++) {  // 子串有2^k种可能
        int bits = 0;
        double mult = 0;
        /*每种可能用bit位表示，最多k位，然后看bit位上是否形成组合*/
        for (int i = 0; i < N; i++) {
            if (msk & (1 << i)) {
                bits++;
                mult += p[i];
            }
        }
        double cur = 1 / mult;
        //cout << cur << endl;
        if (bits % 2 == 1) ans += cur;
        else ans -= cur;
    }
    return ans;
}

int main()
{
    int N;
    double p[25];
    while (cin >> N) {
        for (int i = 0; i < N; i++) cin >> p[i];
        cout << fixed << setprecision(3) << Solve(N, p) << endl;
    }
    return 0;
}