题目大意： 有k只麻球，每只活一天就会死亡，临死之前可能会生出一些新的麻球。具体来说，生i个麻球的概率为Pi,给定m，求m天后所有麻球均死亡的概率。注意，不足m天时就已全部死亡的情况也算在内。
题目分析：设1只麻球在前m天死亡的概率是f[i]，则k只麻球在m天死亡的概率为f[i]^k。转化为子问题。假设前一天所生麻球的数量为j，则f[i]+=f[i-1]^j*p[j]->即当前这一天可以生j只麻球在i-1天内死亡。（可能有点绕自己yy一下。
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<functional> #include<cmath> #include<cctype> #include<cassert> #include<climits> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define ForD(i,n) for(int i=n;i;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define RepD(i,n) for(int i=n;i>=0;i--) #define MEM(a) memset(a,0,sizeof(a)) #define MEMI(a) memset(a,127,sizeof(a)) #define MEMi(a) memset(a,128,sizeof(a)) #define INF (2139062143) #define phiF (1000000006) #define MAXN (1000000+10) typedef long long LL; int T,n,m,k; double p[1005],f[1005]; double po(double x,int y){ double t=1; For (i,y){ t=t*x; } return t; } int main(){ freopen("in.txt","r",stdin); int Case=0; scanf("%d",&T); while (T--){ MEM(f); scanf("%d%d%d",&n,&k,&m); Rep (i,n) { scanf("%lf",&p[i]); } f[0]=0; For (i,m){ double tmp=1; Rep (j,n){ f[i]+=tmp*p[j]; tmp*=f[i-1]; } } printf("Case #%d: ",++Case); printf("%.7f\n",po(f[m],k)); } }
