【参考博客：kuangbin】

【题意】ACM比赛***M道题，T个队,pij表示第i队解出第j题的概率，问，每队至少解决一道题目并且冠军队伍解出n道题目的概率。

【分析&解题思路】dp[i][j][k]表示第i个队，在前j道题中,解决了k道题目的概率！那么dp的转移可以表示为 dp[i][j][j] = dp[i][j-1][k-1]*p[j][k]+dp[i][j-1][k]*(1-p[j][k])；s[i][k]代表第i个队做出的题<=k的概率，s[i][k] = dp[i][M][0]+dp[i][M][1]+...+dp[i][M][k];

那么答案是什么呢？

每个队至少解决出一道题目的概率为p1=(1-s[1][0])*(1-s[2][0])+...+(1-s[n][0]);

每个队做出的题目都在1-(N-1)的范围内的概率p2=(s[1][N-1]-s[1][0])*(s[2][N-1]-s[2][0])*(s[3][N-1]-s[3][0])...(s[T][N-1]-s[T][0]);

答案就是p1-p2.

【AC代码】

//Cloud , you are my sunshine!
//I can't live without you!
//You are the most beautiful girl in the world!
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
double dp[1050][50][50];
double s[1010][50];
double p[1010][50];
int main(){
    int M,T,N;
    while(~scanf("%d%d%d",&M,&T,&N)){
        if(M==0&&T==0&&N==0) break;
        for(int i=1; i<=T; i++)
            for(int j=1; j<=M; j++)
                scanf("%lf",&p[i][j]);
        for(int i=1; i<=T; i++){
            dp[i][0][0]=1;
            for(int j=1; j<=M; j++) dp[i][j][0]=dp[i][j-1][0]*(1-p[i][j]);
            for(int j=1; j<=M; j++)
                for(int k=1; k<=j; k++)
                    dp[i][j][k]=dp[i][j-1][k-1]*p[i][j]+dp[i][j-1][k]*(1-p[i][j]);
            s[i][0]=dp[i][M][0];
            for(int k=1; k<=M; k++) s[i][k]=s[i][k-1]+dp[i][M][k];
        }
        double p1=1.0,p2=1.0;
        for(int i=1; i<=T; i++){
            p1*=(1-s[i][0]);
            p2*=(s[i][N-1]-s[i][0]);
        }
//        double ans=p1-p2;
        printf("%.3f\n",p1-p2);
    }
    return 0;
}