【hdu 4336】Card Collector

### 题目描述 有 $n$ 种卡片，每一秒都有 $p_i$ 的概率获得一张第 $i$ 种卡片，求每张卡片都至少有一张的期望时间 $n \le 20$ ### 题解 考虑 `min-max 容斥`，$E(\max(S))=\sum_{T \subseteq S}(-1)^{\mid T \mid + 1}E(\min(T))$ 考虑 $E(\min(T))$ 的意义，即某个集合的至少获得其中一个元素的期望次数 由于每个元素的获得概率互不相关，因此： $$E(\min(T))=(\sum\limits_{x \in T}p_x)1+(1-\sum\limits_{x \in T}p_x)(E(\min(T)) + 1)$$ 即 $E(\min(T)) = \frac{1}{\sum\limits_{x \in T}p_x}$ 然后枚举子集就行了…… ### 题解 ``` cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 30; int n; double p[N]; void sol() { for(int i = 1 ; i <= n ; ++ i) scanf("%lf", &p[i]); double res = 0; for(int s = 1 ; s < (1 << n) ; ++ s) { int cnt = 0; double sum = 0; for(int i = 1 ; i <= n ; ++ i) { if(s & (1 << (i - 1))) { ++ cnt; sum += p[i]; } } res += (cnt & 1 ? 1.0 : -1.0) / sum; } printf("%.4f\n", res); } int main() { while(scanf("%d", &n) == 1) { sol(); } } ```