UVa11021

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。

#include <cstdio>
#include <cmath>
const int maxn = 1000;
const int maxm = 1000;
int n,k,m;
double P[maxn + 1],f[maxn + 1];// f[i]表示麻球在i天后全死亡的概率
int main(){
    int T; scanf("%d",&T);
    int kase = 0;
    while(T--){
        scanf("%d%d%d",&n,&k,&m);
        for(int i = 0 ; i < n ; i++) scanf("%lf",&P[i]);
        f[0] = 0,f[1] = P[0];
        for(int i = 2 ; i <= m ; i++){
            f[i] = 0;
            for(int j = 0 ; j < n ; j++)
                f[i] += P[j] * pow(f[i - 1],j);
        }
        printf("Case #%d: %.7lf\n",++kase,pow(f[m],k));
    }
    return 0;
}

?