题目描述
Link
LOJ 的题面比 Luogu 的好看qwq
题解
首先根据期望的线性性，最后的答案为 \(\sum\limits_{i = 1}^n a_i * f_i\)，其中 \(f_i\) 表示 \(i\) 真实发动的概率。
为什么 \(f_i\) 不等于 \(p_i\) 呢，因为题中有限制：用了此张牌后进入下个回合，这时候每张牌的概率就变了。
那么考虑计算 \(f\)，令 \(dp_{i, j}\) 表示 \(r\) 轮中在前 \(i\) 张里面取了 \(j\) 张的概率。先把 \(i = 1\) 的算出来 \(dp_{1, 0}\) 是 \(r\) 轮中都没选到 \(1\) 的概率为 \((1 - p_1)^r\)，\(dp_{1, 1}\) 与 \(f_1\) 相等为 \(1 - (1 - p_1)^r\)。
然后考虑 \(dp_{i, j}\) 由什么得来，分类讨论： - 发动第 \(i\) 张牌，那么概率为 \(dp_{i - 1, j - 1} * (1 - (1 - p_i)^{r - j - 1})\)； - 如果不发动，那么概率为 \(dp_{i - 1, j} * (1 - p_i)^{r - j}\)。
最终 \(dp_{i, j}\) 为两个加起来。
那么 \(f_i\) 就是 \(\sum\limits_{j = 0}^r dp_{i - 1, j} * (1 - (1 - p_i)^{r - j})\)，意为在 \(j\) 轮内发动过。
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
| #include <algorithm>
#include <cstdio>
#include <cstring>
const int N = 230;
int d[N];
double p[N], f[N];
double dp[N][N];
double FastPow(double a, int b) {
double res = 1;
for (; b; b >>= 1, a = a * a)
if (b & 1)
res = res * a;
return res;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%lf%d", &p[i], &d[i]);
memset(dp, 0, sizeof(dp));
memset(f, 0, sizeof(f));
dp[1][0] = FastPow(1 - p[1], m);
dp[1][1] = f[1] = 1 - FastPow(1 - p[1], m);
for (int i = 2; i <= n; ++i)
for (int j = 0; j <= std::min(i, m); ++j) {
if (j)
dp[i][j] += dp[i - 1][j - 1] * (1 - FastPow(1 - p[i], m - j + 1));
if (i != j)
dp[i][j] += dp[i - 1][j] * FastPow(1 - p[i], m - j);
}
for (int i = 2; i <= n; ++i)
for (int j = 0; j <= std::min(i - 1, m); ++j)
f[i] += dp[i - 1][j] * (1 - FastPow(1 - p[i], m - j));
double ans = 0;
for (int i = 1; i <= n; ++i)
ans += d[i] * f[i];
printf("%.10lf\n", ans);
}
return 0;
}
|