Organizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect the contest result satisfy the following two terms:
- All of the teams solve at least one problem.
- The champion (One of those teams that solve the most problems) solves at least a certain number of problems.
Now the organizer has studied out the contest problems, and through the result of preliminary contest, the organizer can estimate the probability that a certain team can successfully solve a certain problem.
Given the number of contest problems M, the number of teams T, and the number of problems N that the organizer expect the champion solve at least. We also assume that team i solves problem j with the probability Pij (1 <= i <= T, 1<= j <= M). Well, can you calculate the probability that all of the teams solve at least one problem, and at the same time the champion team solves at least N problems?
-
题意
有M题的概率。 -
解析
涉及到 至少 这个词，不妨使用一些前缀和技巧。
假设p1。
我们需要分别计算每一队的贡献，再把相应的答案乘起来从而计算p1。
设f[i][j]道题的概率。不难发现转移方程为
再利用sum[i]道题的概率，其实就是前缀和。
那么这个队对于p1。 -
数组可以滚，你不滚也没关系
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <cctype>
#include <string>
using namespace std ;
const int maxn = 1005, maxm = 35 ;
int n, m, e ;
double p[maxm], f[2][maxm], sum[maxm] ;
int main() {
int i, j, k ;
while ( scanf ( "%d %d %d", &m, &n, &e ) != EOF ) {
if ( !n ) break ;
double p1 = 1.0, p2 = 1.0 ;
for ( i = 1 ; i <= n ; i ++ ) {
for ( j = 1 ; j <= m ; j ++ )
scanf ( "%lf", &p[j] ) ;
memset ( f, 0.0, sizeof f ) ;
int u, v ;
u = 0, v = 1 ;
memset ( f, 0.0, sizeof f ) ;
f[0][0] = 1.0 ;
for ( j = 1 ; j <= m ; j ++, swap(u, v) )
for ( k = 0 ; k <= j ; k ++ )
f[v][k] = f[u][k-1]*p[j]+f[u][k]*(1-p[j]) ;
sum[0] = f[u][0] ;
for ( j = 1 ; j <= m ; j ++ )
sum[j] = sum[j-1]+f[u][j] ;
p1 *= sum[m]-sum[0] ;
p2 *= sum[e-1]-sum[0] ;
}
printf ( "%.3lf\n", p1-p2 ) ;
}
return 0 ;
}