【题目描述】
万有引力定律：
“使物体相互靠近的力的大小与物体的质量成正比——而物体的质量又由同一种力决定。这是一个有趣并且有益的例子，说明了科学是如何用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
【题解】
全概率公式：假如事件B1,B2,B3…Bn两两之间交集为空且它们的并集就是样本空间,那么对于另一个事件A:
P(A)=P(B1)*P(A|B1)+P(B2)*P(A|B2)…P(Bn)*P(A|Bn)
全概率公式的简单应用，因为每个麻球都是独立的，而且会在当天死亡，未出现新的麻球=全部死亡。设f[i]为一只毛球在i天以内全部死亡的概率。可得
f[i]=p0+f[i-1]*p1+(f[i-1])2*p2+(f[i-1])3*p3...
每只毛球和它的后代死亡的概率是独立的，所以生了1只毛球就是死亡的概率f[i-1]，2只f[i-1]2
最后答案:f[m]k。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int sj=1010; int ca,n,m,k; double p[sj],temp,ww,dxj; int main() {//freopen("t.txt","r",stdin);freopen("tribbles.in","r",stdin);freopen("tribbles.out","w",stdout);scanf("%d",&ca);for(int l=1;l<=ca;l++){scanf("%d%d%d",&n,&k,&m);for(int i=0;i<n;i++) scanf("%lf",&p[i]);ww=p[0];for(int i=2;i<=m;i++){dxj=ww;ww=p[0];temp=dxj;for(int j=1;j<n;j++){ww+=p[j]*temp;temp*=dxj;}}temp=ww;for(int i=2;i<=k;i++)temp*=ww;printf("Case #%d: %.7lf\n",l,temp);}//while(1);return 0; }
