Tribles
Problem's Link:
Mean:
有k个细菌，每个细菌只能存活一天，在死去之前可能会分裂出0,1,2....n-1个细菌，对应的概率为p0,p1,p2....pn-1。
问：所有细菌在第m天全部灭亡的概率是多少？（m天以前灭亡也算在内）
analyse:
由于每一个细菌的生存是独立的，所以我们可以先算出一个细菌的概率为PP，最终答案应是：PP^k。
设dp[i]表示第i天全部灭亡的概率，那么：
dp[i] = p0*(dp[i-1]^0) + p1*(dp[i-1]^1) + p2*(dp[i-1]^2) + ...pn-1*(dp[i-1]^(n-1))
其中pi*(dp[j-1]^i)表示：该细菌分裂成了i个，这i个细菌在第j-1天灭亡的概率。
由于每个细菌独立，所以是乘法，也就是i次方。
对于dp[0]，代表第0天就全部灭亡，也就是根本没有分裂，所以dp[0]=p0.
Time complexity: O(N)
Source code:
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-08-26-20.36 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std;
typedef long long(
LL);
typedef unsigned long long(
ULL);
const double eps(
1e-8);
const int MAXN = 1010;
double p
[ MAXN ], dp [ MAXN ]; int main()
{ ios_base :: sync_with_stdio(
false);
cin . tie(
0);
int t;
scanf(
"%d" , & t);
for(
int Cas = 1;
Cas <= t;
++ Cas)
{ int n
, k , m;
scanf(
"%d %d %d" , &n
, & k , & m);
for(
int i = 0;
i <n;
++ i)
scanf(
"%lf" , &p
[ i ]); dp [ 0 ] =p
[ 0 ]; for(
int i = 1;
i < m;
++ i)
{ dp [ i ] = 0.;
for(
int j = 0;
j <n;
++ j)
{ dp [ i ] +=p
[ j ] * pow(
dp [ i - 1 ], j);
} } printf(
"Case #%d: %.7f \n " , Cas , pow(
dp [ m - 1 ], k));
} return 0;
} /* */