「UVa 11021」Tribles - 概率与期望

个 Tribles,每个 Trible 只能存活一天,但在死亡之前,每个 Trible 有 的概率繁衍出 个 Tribles。求 天之后所有 Tribles 全部死亡的概率。

链接

UVa 11021
COGS 1487

题解

为一个 Trible 经过 天后全部死亡的概率,则 个 Trible 经过 天后全部死亡的概率为

根据题意,每个 Trible 每天的繁衍行为共分为 种情况,每一种情况发生的概率乘以繁衍出的 Tribles 在剩余的 天全部死亡的概率的总和即为结果。

边界条件为

代码

#include <cstdio>
#include <cmath>
#include <algorithm>

const int MAXN = 1000;
const int MAXK = 1000;
const int MAXM = 1000;

int main() {
    int t, n, k, m;
    scanf("%d", &t);
    for (int i = 1; i <= t; i++) {
        scanf("%d %d %d", &n, &k, &m);
        static double p[MAXN], f[MAXK + 1];
        for (int i = 0; i < n; i++) scanf("%lf", &p[i]);
        std::fill(f, f + m + 1, 0);
        f[0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < n; j++) {
                f[i] += p[j] * pow(f[i - 1], j);
            }
        }
        printf("Case #%d: %.7lf\n", i, pow(f[m], k));
    }

    return 0;
}