题目描述
小时候，谷学长买了很多干脆面，因为一旦集齐所有类型的卡片就有大奖可拿。
谷学长很聪明的意识到要想集齐全套卡片就得买相当多的干脆面，为了尽可能的省钱，他想计算出每种类型卡片均获得一张应买干脆面的期望数目。
输入
每个测试用例的第一行包含一个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]
- E(C) = C
- E(CX) = CE(X)
- 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;
}
