【概率】COGS 1487:麻球繁衍


Description

  万有引力定律:

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

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

Input

  输入包含多组数据。

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

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

  接下来有n行,给出P_0,P_1,…,P_n-1。

Output

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


  首先这题我们设f[i]为一只毛球在i天以内全部死亡的概率。可得

  f[i]=p0+f[i-1]*p1+(f[i-1])2*p2+(f[i-1])3*p3...

  每只毛球和它的后代死亡的概率是独立的,所以生了1只毛球就是p1的几率*死亡的几率f[i-1],2只f[1-1]2(乘法原理)

  最后答案:f[m]k

  

 #include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm> using namespace std; double qvod(double x,int k)
{
double ans=;
while(k)
{
if(k&)ans=ans*x;
x=x*x;
k>>=;
}
return ans;
} double f[],gg[]; int main()
{
freopen("tribbles.in","r",stdin);
freopen("tribbles.out","w",stdout);
int n,k,T,m,b=;
scanf("%d",&T);
while(T--)
{
b++;
scanf("%d%d%d",&n,&k,&m);
for(int i=;i<n;i++)
scanf("%lf",&gg[i]);
f[]=,f[]=gg[];
for(int i=;i<=m;i++)
{
f[i]=;
for(int j=;j<n;j++)
{
f[i]+=gg[j]*qvod(f[i-],j);
}
}
printf("Case #%d:%.7lf\n",b,qvod(f[m],k));
}
return ;
}
上一篇:Java代理(静态/动态 JDK,cglib)


下一篇:【转】Swing 与EDT线程