题意:有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)的复杂度内求解啦!