数论-概率手机卡片 2012 Multi-University Training Contest 4

假设有卡片 1, 2, 3 ，用 F(S) 表示在已拿到 S 集合表示的卡片时还需要购买的卡片期望值

答案为 F(Ø) , F(U) = 0 (U 是全集，就是已得到所有卡片)

分别考虑每次买卡时 1.得到新卡 2.得到重复的卡片或没有得到卡片的情况

比如 F({1}) = F({1, 2, 3}) * (p2 + p3) + F({1}) * (1 - p2 - p3) + 1

情况1 情况2

严谨一点就是

F(S) = F({S υ A}) * ∑p_i + F(S) * (1 - ∑p_i) + 1

其中 A 是没有得到的卡片， pi 是给出的得到这些卡片的概率

得到 F(S) = F({S υ A}) + 1 / ∑p_i

考虑到精度问题，可以变成

F(S) = (∑p_i * F({S υ A}) + 1) / ∑p_i

顺序枚举 S υ A 和 A，这道题很适合二进制子集构造法（全集 U = 1<<N 最大才 1024*1024 ，数组开得下），当然写搜索也可以过。

 1 #include <stdio.h>
 2 
 3 typedef long long LL;
 4 
 5 const int _N = 22;
 6 
 7 double f[1<<_N], p[_N];
 8 
 9 int main()
10 {
11     LL n, FULL, i, j;
12     double sump;
13     scanf("%lld", &n);
14     for (i = 1; i <= n; ++i)
15         scanf("%lf", &p[i]);
16     f[FULL = (1<<n) - 1] = 0;
17     for (i = FULL-1; i >= 0; --i) {
18         f[i] = 1, sump = 0;
19         for (j = 0; j < n; ++j) {
20             if ((i>>j) & 1 ^ 1)
21                 f[i] += f[i | (1<<j)] * p[j+1], sump += p[j+1];
22         }
23         f[i] /= sump;
24     }
25     printf("%.6lf
", f[0]);
26     return 0;
27 }

题目:NKOJ2127

P2127【概率】搜集卡片

时间限制 : 10000 MS 空间限制 : 65536 KB

问题描述

童年时代，你是否热衷于搜集零食里的卡片呢？比如你集齐了108张水浒英雄的卡片，你会感到非常有成就感，而且还可以去兑换奖品。

作为一个聪明的小孩，你注意到如果你要赢得奖品，你必须买很多很多的零食才能搜集齐卡片。要赢得奖品，你估计要买多少袋零食才能成功？

输入格式

第一行，一个整数N(1 <= N <= 20), 表示总共有N种不同的卡片。
第二行，N个空格间隔的实数p1, p2, ..., pN, (p1 + p2 + ... + pN <= 1), 表示零食袋中每种卡片出现的概率。
注意：一包零食中最多有一张卡片，也可能一张都没有。

输出格式

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

样例输入

2
0.1 0.4

样例输出

10.500000

来源 2012 Multi-University Training Contest 4