Description：

给出队伍 $i$ 解决题目 $j$ 的概率 $p[i][j]$ ，求所有队伍都至少解决一题且冠军至少解决了 $k$ 道题的概率。

$1\le n \le 1000,1\le m \le 30$

Solution：

答案很不好算，考虑正难则反，用所有队伍都解决了一道题的概率 $P1$ 减去所有队伍解决的题目数都在 $[1,k-1]$ 之间的概率 $P2$ 。

设 $f[i][j][k]$ 表示第 $i$ 支队伍在前 $j$ 道题目中做出 $k$ 道的概率， $f[i][j][k] = f[i][j-1][k-1]\times p[i][j]+f[i][j - 1][k]\times(1 - p[i][j])$ .

$\begin{align}s[i][k]=\sum_{i=0}^mf[i][m][i]\end{align}$

$s[i][m]-s[i][0]$ 表示第 $i$ 支队伍至少做出一题的概率。

$s[i][k-1]-s[i][0]$ 表示第 $i$ 支队伍做出的题目在 $[1,k-1]$ 之间的概率。

其实就是前缀和。

$$\begin{align}P1=\prod_{i=1}^n(s[i][m] - s[i][0])\end{align}$ $

$$\begin{align}P2=\prod_{i=1}^n(s[i][k-1] - s[i][0])\end{align}$ $

最终结果 $$P=P1-P2$ $

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int m,n,k;

#define MAXM 35

#define MAXN 1010

double p[MAXN][MAXM];

double f[MAXN][MAXM][MAXM];

double s[MAXN][MAXM];

int main()

{

	while(scanf("%d%d%d",&m,&n,&k) && m != 0 && n != 0 && k != 0)

	{

		memset(f,0,sizeof(f));

		memset(s,0,sizeof(s));

		double P1 = 1,P2 = 1;

		for(int i = 1;i <= n;++i)

			for(int j = 1;j <= m;++j)

				scanf("%lf",&p[i][j]);

		for(int i = 1;i <= n;++i)

		{

			f[i][0][0] = 1;

			for(int j = 1;j <= m;++j)

			{

				for(int k = 0;k <= j;++k)

				{

					f[i][j][k] += f[i][j - 1][k] * (1 - p[i][j]);

					if(k > 0)f[i][j][k] += f[i][j - 1][k - 1] * p[i][j];

				}

			}

			s[i][0] = f[i][m][0];

			for(int j = 1;j <= m;++j)

			{

				s[i][j] = s[i][j - 1] + f[i][m][j];

			}

			P1 = P1 * (s[i][m] - s[i][0]);

			P2 = P2 * (s[i][k - 1] - s[i][0]);

		}

		printf("%.3lf\n",P1 - P2);

	}

	return 0;

}