poj 2151(概率DP)

poj 2151
设$dp(i, j, k)$为选手$i$在前$j$题中做对$k$题的概率，则转移方程为
$$dp(i,j,k)=dp(i,j-1,k-1) \times p(i,j) + dp(i,j-1,k) \times (1-p(i,j))$$
初始化的时候$dp(i,0,0)=1, dp(i,j,0)=dp(i,j-1,0) \times (1-p(i,j))$
然后因为我们要求出所有选手做对一题且有选手做出大于等于$n$题，所以这是个容斥问题，即可以用所有选手至少做对一题的概率$P_1$减去所有选手做对题目个数在$[1, n-1]$之间的概率$P_2$的差即为答案，怎么求呢？
设$s(i,j)$为选手$i$做对至多$j$题的概率，则$s(i,j)= \sum_{k=0}^{j} dp(i, k)$
则$P_1= \prod_{i=1}^{t}(1-s(m, 0)) $
$P_2= \prod_{i=1}^{t}(s(m, n-1)-s(m, 0)) $
$P_1 - P_2$即为答案(容斥原理)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXM = 50 + 5, MAXT = 1000 + 10;
int m, t, n;
db p[MAXT][MAXM], dp[MAXT][MAXM][MAXM], s[MAXT][MAXM];
void clean() {
    ms(dp, 0);
}
void solve() {
    clean();
    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]);
            }
        }
    }
    for (int i=1;i<=t;i++) {
        s[i][0] = 0;
        for (int j=0;j<=m;j++) s[i][j] = s[i][j - 1] + dp[i][m][j];
    }
    db p1 = 1, p2 = 1;
    for (int i=1;i<=t;i++) p1 *= (1 - s[i][0]);
    for (int i=1;i<=t;i++) p2 *= (s[i][n-1] - s[i][0]);
    printf("%.3f\n", p1 - p2);
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin); freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d%d%d", &m, &t, &n)&&(m||t||n)) solve();
    fclose(stdin); fclose(stdout);
    return 0;
}