题解 UVA11021 【Tribles】
Ezio_0420
2018-02-27 14:33:34
只要知道全概率公式，这就是一道水题。因为麻球的各种活动都互不影响，所以现在只考虑一只麻球，我们假设f[i]是第i天全部都死亡的概率，那么
f[i] = p0 + p1*f[i-1] + p2*f[i-1]^2 + ...pn-1*f[i - 1]^(n-1)
也就是用前一天的全部死亡概率来代替今天的每一只死亡的概率，又因为今天的每只的生死概率什么的都是独立的，所以p2*f[i-1]^2可以理解成剩下2只，然后两只都死了，这样最后在第m天死光的概率就是f[m]，但是这个只是一只麻球的，所有麻球都死光是f[m]^k。
```cpp
#include<cstdio>
#include<cmath>
const int maxn = 1000 + 10;
const int maxm = 1000 + 10;
int n, k, m;
double P[maxn], f[maxm];
int main() {
int T;
scanf("%d", &T);
for(int kase = 1; kase <= T; kase++) {
scanf("%d%d%d", &n, &k, &m);
for(int i = 0; i < n; i++) scanf("%lf", &P[i]);
f[0] = 0; f[1] = P[0];
for(int i = 2; i <= m; i++) {
f[i] = 0;
for(int j = 0; j < n; j++) f[i] += P[j] * pow(f[i-1], j);
}
printf("Case #%d: %.7lf\n", kase, pow(f[m], k));
}
return 0;
}
```