「UVa 11021」Tribles - 概率与期望

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

链接

UVa 11021
COGS 1487

题解

f(i) 为一个 Trible 经过 i 天后全部死亡的概率,则 x 个 Trible 经过 i 天后全部死亡的概率为 f(i) ^ x

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

边界条件为 f(0) = 1

f(i) = \sum\limits_{j = 0} ^ {n - 1} f(i - 1) ^ j \times p(j)

代码

#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;
}