1487. [UVa 11021] 麻球繁衍

【题目描述】

万有引力定律：

“使物体相互靠近的力的大小与物体的质量成正比——而物体的质量又由同一种力决定。这是一个有趣并且有益的例子，说明了科学是如何用 $A$ 证明 $B$，再用 $B$ 证明 $A$ 的。”——安布罗斯·比尔斯（美国讽刺作家——译者注）。

你有一坨 $K$ 个毛球（<星际迷航>中的种族——译者注）。这种毛球只会存活一天。在死亡之前，一个毛球有 $P_i$ 的概率生出 $i$ 个毛球 $(i=0,1,...,n-1)$。$m$ 天后所有毛球都死亡的概率是多少？（包含在第 $m$ 天前全部死亡的情况）

【输入格式】

输入包含多组数据。

输入文件的第 $1$ 行是一个正整数 $N$，表示数据组数。

每组数据的第 $1$ 行有 $3$ 个正整数 $n(1<=n<=1000),k(0<=k<=1000),m(0<=m<=1000)$。

接下来有 $n$ 行，给出 $P_0,P_1,...,P_{n-1}$。

【输出格式】

对于第 $i$ 组数据，输出"Case #i: "，后面是第 $m$ 天后所有毛球均已死亡的概率。

【样例输入】

4
3 1 1
0.33
0.34
0.33
3 1 2
0.33
0.34
0.33
3 1 2
0.5
0.0
0.5
4 2 2
0.5
0.0
0.0
0.5

【样例输出】

Case #1: 0.3300000
Case #2: 0.4781370
Case #3: 0.6250000
Case #4: 0.3164063

【提示】

如果你的输出与标准答案相差不超过 $10^{-5}$，那么你的答案就被认为是正确的。

【来源】

UVa11021 Tribles

刘汝佳，《算法竞赛入门经典训练指南》表2.8