题目描述
https://www.luogu.com.cn/problem/UVA11021
简要题意：一开始有 $k$ 个生物，这种生物只能活一天，死亡时有 $p_i,i\in[0,n-1]$ 的概率产生 $i$ 只这种生物，求 $m$ 天内所有生物都死亡的概率
$n,k,m\le 1000$
Solution
我们令 $f[i]$ 表示一只麻球及其后代在 $i$ 天内全部死掉的概率，注意到每只麻球都可以独立计算
然后我们有以下转移，$f[i]=\sum_{j=0}^{n-1}p[j]f^j[i]$
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
| #include <iostream>
#include <cstdio>
#include <iomanip>
#define maxn 1010
#define ll long long
using namespace std;
int n, k, m;
double f[maxn], p[maxn]; int icase;
void work() {
cin >> n >> k >> m;
for (int i = 0; i < n; ++i) cin >> p[i];
f[1] = p[0];
for (int i = 1; i <= m; ++i) {
f[i] = 0; double pow = 1;
for (int j = 0; j < n; ++j) {
f[i] += pow * p[j];
pow *= f[i - 1];
}
}
double ans = 1;
for (int i = 1; i <= k; ++i) ans *= f[m];
cout << "Case #" << ++icase << ": " << fixed << setprecision(7) << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|