Card Collector
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3001 Accepted Submission(s): 1435
Special Judge
As a smart boy, you notice that to win the award, you must buy much more snacks than it seems to be. To convince your friends not to waste money any more, you should find the expected number of snacks one should buy to collect a full suit of cards.
Note there is at most one card in a bag of snacks. And it is possible that there is nothing in the bag.
You will get accepted if the difference between your answer and the standard answer is no more that 10^-4.
0.1
2
0.1 0.4
10.500
求期望
方法一：状压
逆序枚举所有状态 d[i] 表示状态为i时收集完所有卡片的期望步数。
d[i] = 1 + ∑(d[i | (1 << j)] * p[j])(ps: 累加所有走一步会增加新一张卡片的期望步数) + (1 - t) * d[i](ps: t为增加一张新卡片的概率);
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define ll long long
#define _cle(m, a) memset(m, a, sizeof(m))
#define repu(i, a, b) for(int i = a; i < b; i++)
#define MAXN (1 << 20) double d[MAXN + ];
double p[];
int main()
{
int n;
while(~scanf("%d", &n))
{
memset(d, , sizeof(d));
repu(i, , n) scanf("%lf", &p[i]);
if(( << n) - ) d[( << n) - ] = 0.0;
double t;
for(int i = ( << n) - ; i >= ; i--)
{
d[i] += 1.0;
t = 0.0;
for(int j = ; j < n; j++)
if(!(i & ( << j))) {
d[i] += p[j] * d[i | ( << j)];
t += p[j];
}
d[i] /= t;
}
printf("%.4lf\n", d[]);
} return ;
}
方法二：容斥
设Ai表示取到第i张卡片的期望，Ai = 1 / pi;
由容斥原理得：
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define ll long long
#define _cle(m, a) memset(m, a, sizeof(m))
#define repu(i, a, b) for(int i = a; i < b; i++)
#define MAXN (1<<20) double p[];
double d[MAXN + ];
int main()
{
int n;
while(~scanf("%d", &n))
{
double re = 0.0;
repu(i, , n) scanf("%lf", &p[i]);
int m = ;
double t = 0.0;
repu(i, , ( << n)) {
m = , t = 0.0;
repu(j, , n) if(i & ( << j)) t += p[j], m++;
if(m & ) re += 1.0 / t;
else re -= 1.0 / t;
}
printf("%.4lf\n", re);
}
return ;
}