NKOJ 2127搜集卡片（数学期望状态压缩递推）

P2127【概率】搜集卡片

问题描述

童年时光里有没有对收集零食中的小贴纸或卡片这件事很感兴趣？比如说当你集齐了108张水浒传里的英雄卡时会为自己能拥有这么多稀有的卡而感到自豪并且还能兑换奖品。

作为一个机灵的孩子你会发现如果想要获得奖品你需要购买大量的零食来完成你的收集目标那么你估计自己需要购买多少袋零食才有可能集齐所有卡片呢？

输入格式

给定一个整数N(1 ≤ N ≤ 20)，代表所有不同种类的卡片总数。

在第二行中给出的是以空格分隔的实数p₁至p_N（满足p₁+p₂+…+p_N ≤ 1），这些数值代表了每种卡片在零食袋中的出现概率。

请注意，在任意一包零食中最多只能包含一张卡片，并不排除完全不含任何卡片的可能性。

输出格式

一个实数，表示你计算的结果，保留6位小数

样例输入

2
0.1 0.4

样例输出

10.500000

---

考虑到n的具体取值范围（也就是n的范围），自然会联想到状态压缩的方法。我们可以用二进制数S来表示当前已收集到不同种类卡片的数量情况。定义F[S]为从当前状态出发收集完所有卡片所需的零食期望数量。举个例子说：假设我现在手里有若干卡片，则F[S]就等于这个情况下所需