题意：有 k 只 Tribles , 每一只 Trible 可以恰好活一天，第二天会死，死的时候生下一些小 Tribles, 每只小 Trible 继续活和生仔。现在要知道第 m 天时没有 Trible 的概率是多少。已知每一只 Trible 产下的小 Trible 的数量为 [0,n-1], 概率分别为 $P_0,P_1,*,P_{n-1}$，也就是产下 i 只的概率为 $P_i$(m,n,k∈[0,1000], 有多组数据)

思路：很自然地想到用 f[i][j] 表示第 i 天有 j 只 Trible 地概率，递推即可。问题是对于每个状态我们又要花 O(m) 转移，所以绝对行不通。

那么如果直接用 f[i] 表示第 i 天没有 Trible 的概率呢？其实可以。首先明确一个事实：我们只需要知道对于 1 只 Trible 的 f[i]，答案最后取 k 次幂即可。现在如果要求第 i 天没有 Trible 的概率，那么首先你得让第一只 Trible 生的孩子死光，那么就是 $f[i-1]^x$, 其中 x 为生的数量 (每一只都得死，所以是 x 只的概率乘起来)。所以得出一个优美的公式

\begin{equation}
f[i]=\sum_{i=0}^{n-1}{P_i*f[i-1]^i}
\end{equation}

这样就可以在 O(nm) 的复杂度内求解啦！

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

#define MX 1005

using namespace std;

int n,k,m;
double p[MX],f[MX];

void input()
{
    scanf("%d%d%d",&n,&k,&m);
    for(int i=0;i<=n-1;i++)scanf("%lf",&p[i]);
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int w=1;w<=t;w++)
    {
        input();
        memset(f,0,sizeof(f));
        for(int i=1;i<=m;i++)
            for(int j=0;j<=n-1;j++)
                f[i]+=pow((double)f[i-1],j)*p[j];
        printf("Case #%d: %.7f\n",w,pow(f[m],k));
    }
    return 0;
}