Tribles UVA

题意：

　　有k只麻球，每只只活一天，临死之前可能会出生一些新的麻球，

具体出生i个麻球的概率为P，给定m，求m天后麻球全部死亡的概率。

解析：

　　从小到大，先考虑一只麻球的情况  设一只麻球m天后全部死亡的概率为f（m）

则第i天全部死亡的概率为f（i）  这一只麻球有多种情况，不生孩子，生一个，生两个，········

那么因为需要i天后全部死亡， 则孩子最多能繁衍到i天 即孩子最多繁衍（i-1）天  （因为孩子从第二天才出来 比父少一天）、

所以孩子i天后全部死亡的概率为f（i-1）

所以 f（i）= P0 + P1*f（i-1） + P2*f（i-1）^2 + P3 * (i-1)^3+····+Pn-1*f(i-1)^n-1;

递推就好了

 

import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        final int maxn = 10010;
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        int cnt = 0;
        while(T-- != 0)
        {
            double[] P = new double[maxn];
            double[] f = new double[maxn];
            int n = cin.nextInt();
            int k = cin.nextInt();
            int m = cin.nextInt();
            for(int i=0;i<n;i++)
                P[i] = cin.nextDouble();
            f[1] = P[0];
            for(int i=2;i<=m;i++)
                for(int j=0;j<n;j++)
                    f[i] += P[j] * Math.pow(f[i-1], j);
            f[m] = Math.pow(f[m], k);
            DecimalFormat s = new DecimalFormat("0.0000000");
            System.out.println("Case #" + ++cnt + ":" + s.format(f[m]));
    
        }
        
    }
}