11021 Tribbles
GRAVITATION, n.
“The tendency of all bodies to approach one another with a strength
proportion to the quantity of matter they contain – the quantity of
matter they contain being ascertained by the strength of their tendency
to approach one another. This is a lovely and edifying illustration of
how science, having made A the proof of B, makes B the proof of A.”
Ambrose Bierce
You have a population of k Tribbles. This particular species of Tribbles live for exactly one day and
then die. Just before death, a single Tribble has the probability Pi of giving birth to i more Tribbles.
What is the probability that after m generations, every Tribble will be dead?
Input
The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line
containing n (1  n  1000), k (0  k  1000) and m (0  m  1000). The next n lines will give the
probabilities P0; P1; : : : ; Pn??1.
Output
For each test case, output one line containing ‘Case #x:’ followed by the answer, correct up to an
absolute or relative error of 10??6.
Sample Input
43
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
Universidad de Valladolid OJ: 11021 – Tribbles 2/2
Sample Output
Case #1: 0.3300000
Case #2: 0.4781370
Case #3: 0.6250000
Case #4: 0.3164062

题意：

       有k只麻球，每只活一天就会死亡，临时前可能会产生一些新的麻球。产生i(0<=i<=n)个麻球的概率是Pi。给定m，求m天（或者不足m天）之后所有麻球都死亡的概率。

分析：

       由于每只麻球的后代独立存活，只需要求出一开始只有1只麻球，m天会全部死亡的概率f(m)。由全概率公式：

       f(i) = P0 + P1 * f(i - 1) + P2 * f(i - 1) ^ 2 + … + Pn * f(i - 1) ^ n。

最终答案为f(m) ^ k。

 1 #include <cstdio> 2 #include <cmath> 3 const int maxn = 1000; 4 const int maxm = 1000; 5 int n,k,m; 6 double P[maxn + 1],f[maxn + 1];// f[i]表示麻球在i天后全死亡的概率 7 int main(){ 8     int T; scanf("%d",&T); 9     int kase = 0;10     while(T--){11         scanf("%d%d%d",&n,&k,&m);12         for(int i = 0 ; i < n ; i++) scanf("%lf",&P[i]);13         f[0] = 0,f[1] = P[0];14         for(int i = 2 ; i <= m ; i++){15             f[i] = 0;16             for(int j = 0 ; j < n ; j++)17                 f[i] += P[j] * pow(f[i - 1],j);18         }19         printf("Case #%d: %.7lf\n",++kase,pow(f[m],k));20     }21     return 0;22 }

View Code

UVa11021