1 /*UVA 11021
2 繁衍问题:
3 总结:不同个体都可以看成相互独立的事件,即每个个体后代单独存货
4 输入: n (1<= n<=1000) , k (0<= k<=1000) and m (0<= m<=1000)
5 n:可能生产数 k:初始生命体数 m:m天都全部死亡
6 p[0] ,p[1]...p[n-1]:p[i]产生i个后代的概率
7 输出:m天后全部死亡的概率
8 递推公式:f[x]:1个生命体x天后死亡的概率
9 kf[k,x]:k个生命体x天后死亡的概率
10 f[x]=p[0]+p[1]*kf[1,x-1]+p[2]*kf[2,x-1].....p[n-1]*kf[n-1,x-1];
11 kf[k,x]=f[x]^k;相互独立
12 边界条件:f[1]=p[0];
13 */
14 #include<iostream>
15 #include<stdio.h>
16 #include<string.h>
17 #include<algorithm>
18 #include<stdlib.h>
19 #include<math.h>
20 #include<queue>
21 #include<vector>
22 #include<map>
23
24 using namespace std;
25
26
27 int k,n,m;
28 double p[1005],f[1005];
29 /*double f(double d)
30 {
31 if (d==1) return p[0];
32 double ans=p[0];
33 for(int i=1;i<=n-1;i++) ans+=p[i]*pow(f(d-1),i);
34 return ans;
35 } 迭代次数多,RE*/ //注意
36 int main()
37 {
38 int t;
39 cin>>t;
40 for(int cas=1;cas<=t;cas++)
41 {
42 cin>>n>>k>>m;
43 for(int i=0;i<n;i++) cin>>p[i];
44 f[1]=p[0];
45 for(int i=2;i<=m;i++)
46 {
47 f[i]=p[0];
48 for(int j=1;j<=n-1;j++) f[i]+=p[j]*pow(f[i-1],j);
49 }
50 cout<<"Case #"<<cas<<": ";
51
52 printf("%.7lf
",pow(f[m],k));
53 }
54 }