有nn种卡片，第ii种出现的概率为pip_i（∑pi\sum p_i不一定为11），问收集所有卡片的期望次数

n≤20n\le 20

HDU4336

Solution & Code

傻逼题，有两种做法：

暴力Dp

dp[i]dp[i]表示从集合ii开始的期望次数，直接枚举下一个没在当前集合中出现的元素yy，设 ，用NoNo表示没有抽中卡片的概率（即1−∑i=1npi1 - \sum_{i=1}^{n} p_i）那么很显然有方程：

dp[i]=∑dp[j]py+dp[i](∑z∈ipz+No)+1 dp[i] = \sum dp[j]p_y + dp[i](\sum_{z\in i}p_z + No) + 1

化简得到

dp[i]=∑dp[j]py+11−∑z∈ipz−No dp[i] = \frac{\sum dp[j]p_y + 1}{1 - \sum_{z\in i}p_z - No}

写得好看一点就是

dp[i]=∑dp[j]py+1∑py dp[i] = \frac{\sum dp[j]p_y + 1}{\sum p_y}

答案就是dp[0]dp[0]

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 20 + 5, Maxs = (1 << 20) + 100;

int N;
double P[Maxn], Dp[Maxs], No;

inline void Solve ()
{
	memset(Dp, 0, sizeof Dp);
	int ALL = (1 << N) - 1;

	for (int state = ALL - 1; state >= 0 ; --state)
	{
		double sum = 0;

		for (int i = 1; i <= N; ++i)
		{
			if ((1 << (i - 1)) & state) { sum += P[i]; continue;}
			int to = state | (1 << (i - 1));
			Dp[state] += Dp[to] * P[i];
		}

		++Dp[state];
		Dp[state] /= (1 - sum - No);
	}
	printf("%.5lf\n", Dp[0]);
}

inline void Input ()
{
	No = 0;
	for (int i = 1; i <= N; ++i) scanf("%lf", &P[i]), No += P[i];
	No = 1 - No;
}

int main()
{
#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	while (scanf("%d", &N) != EOF)
	{
		Input();
		Solve();
	}
	return 0;
}

Min-Max容斥

用Min−MaxMin-Max容斥的套路，将集合内最后一个元素出现的期望次数转化为求这个集合中最早出现的元素的期望次数，即

用和之前dp类似的推式子的方法可以得到

直接dfs搜子集即可

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 20 + 5;

int N;
double P[Maxn], ans;

inline void dfs (int x, double sum, int op)
{
	if (x == N) { if (sum > 1e-7) ans += op / sum; return ; }
	dfs(x + 1, sum + P[x + 1], -op);
	dfs(x + 1, sum, op);
}

inline void Solve ()
{
	ans = 0;
	dfs(0, 0, -1);
	printf("%.6lf\n", ans);
}

inline void Input ()
{
	for (int i = 1; i <= N; ++i) scanf("%lf", &P[i]);
}

int main()
{
#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	while (scanf("%d", &N) != EOF)
	{
		Input();
		Solve();
	}
	return 0;
}