题目链接
有 $k$ 只麻球，每只活一天就会死亡，临死前可能会生出一些新的麻球。具体来说，生 $i$ 只麻球的概率为 $P_i$ 。给定 $m$ ，求 $m$ 天后所有麻球均死亡的概率。
我感谢我自己
每只麻球均可视为一个独立的问题。设 $f[i]$ 表示第一天只有 $1$ 只麻球，在第 $i$ 天它及它的后代全部死亡的概率。由全概率公式，有
$$
f[i]=P_0+P_1f[i-1]+P_2f[i-1]^2+P_3f[i-1]^3+…+P_{n-1}f[i-1]^{n-1}
$$
其中 $P_jf[i-j]^j$ 的含义是这个麻球生了 $j$ 个后代，并且它们在 $i-1$ 天后全部死亡的概率。由于一开始有 $k$ 只麻球，最终答案为 $f[m]^k$ 。
代码如下：
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
| #include<bits/stdc++.h>
using namespace std;
int T;
int N, K, M;
double P[1005];
double f[1005];
int main() {
cin >> T;
for (register int Case = 1; Case <= T; ++Case) {
cin >> N >> K >> M;
for (register int i = 0; i < N; ++i)
cin >> P[i];
f[0] = 0;
for (register int i = 1; i <= M; ++i) {
f[i] = 0;
for (register int j = 0; j < N; ++j)
f[i] += P[j] * pow(f[i - 1], j);
}
cout << "Case #" << Case << ": ";
cout << fixed << setprecision(8) << pow(f[M], K) << endl;
}
return 0;
}
|