题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33059
【思路】
递推+概率。
设f[i]表示一只Tribble经过i天之后死绝的概率,则有递推式:
f[i]=p[0]+p[1]*(f[i-1]^1)+…p[n-1]*(f[i-1]^n-1)
最后答案为f[m]^k
【代码】
#include<cstdio>
#include<cstring>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; const int N = +; double p[N] , f[N];
int n,m,k; double pow(double x,int p) {
double ans=,tmp=x;
while(p) {
if(p&) ans*=tmp;
tmp*=tmp; p>>=;
}
return ans;
} int main() {
int T,kase=;
scanf("%d",&T);
while(T--) {
scanf("%d%d%d",&n,&k,&m);
FOR(i,,n-) scanf("%lf",&p[i]);
f[]=; f[]=p[];
FOR(i,,m) {
f[i]=;
FOR(j,,n-) f[i]+=p[j]*pow(f[i-],j);
}
printf("Case #%d: %.7lf\n",++kase,pow(f[m],k));
}
return ;
}