学步园

本题是很一般的概率问题，不过突然遇到感觉手足无措，可能是因为概率论学的不是很扎实吧！根据题意我们可以设

事件A="每个队伍至少出1题"，事件B="存在一个队伍至少出N题"

我们要求的是：P(AB), 然而这个不是很好求，那么我们换一种方法来解决，就是利用公式转化一下，我们知道

P(A)=P(A(B+!B))=P(AB)+P(A!B)

那么我们可以很轻松的得到：P(AB)=P(A)-P(A!B)

P(A)和P(A!B)利用乘法原理是很容易求出来的，因此接下来就不是问题了，为了代码实现简单，在一个

地方透风减料，结果WA了一次，还是明白之后再向上提交，不要半知半解就往上面提交。

/* 
 * File:   main.cpp
 * Author: hitacm
 *
 * Created on September 2, 2012, 12:54 PM
 */

#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXT = 1011;
const int MAXM = 32;
int M, T, N;
double P[MAXT][MAXM];
double dp[MAXT][MAXM][MAXM];

double DFS(int i, int pos, int num)
{
    if (num < 0 || pos < num) return 0;
    if (pos <= 0) return 1;
    if (dp[i][pos][num] >= 0) return dp[i][pos][num];
    dp[i][pos][num] = DFS(i, pos - 1, num - 1) * P[i][pos] + DFS(i, pos - 1, num)*(1 - P[i][pos]);
    return dp[i][pos][num];
}

double get_result()
{
    for (int i = 1; i <= T; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            for (int k = 0; k <= M; k++)
            {
                dp[i][j][k] = -1;
            }
        }
    }

    double A = 1;
    double B = 1;
    for (int i = 1; i <= T; i++)
    {
        double temp1 = 0;
        for (int j = 1; j <= M; j++)
        {
            temp1 += DFS(i, M, j);
            if (j == N - 1)
            {
                B *= temp1;
            }
        }
        A *= temp1;
    }
    if (N > 1)
    {
        return A - B;
    }
    else
    {
        return A;
    }
}

int main()
{
    while (scanf("%d%d%d", &M, &T, &N))
    {
        if (M == 0 && N == 0 && T == 0)
        {
            break;
        }
        for (int i = 1; i <= T; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                scanf("%lf", &P[i][j]);
            }
        }
        printf("%.3lf\n", get_result());

    }
    return 0;
}