zoj3822-概率dp-Domination

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3822
给定一个棋盘，m*n这么大，要求你在这个棋盘上面放棋子，要求每行每列至少都要有一个。问你期望有多少。。
我的一开始的想法是先用组合数学什么乱七八糟的东西球出来所有的方案数（以为方案数可以递推过来，然后直接计算期望就好了）
但是推的时候好像就推错了，然后就不知道怎么办了。
后来看了题解，mmp概率dp
首先求出 放置到前i行 前j列时刻，棋盘中 放置 k棋子个数的 概率。
然后递推。
我们发现，总共四种状态。
1 当前行当前列有，我们可以在之前已经合法的地方在加一个。
2当前列没有 n-j+1 *i
3 当前行没有
4 当前行 当前列都没有 ，

#include <queue>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
double dp[55][55][3005];
int main(){
     int t;
     int m,n;
     scanf("%d",&t);
     while(t--)
     {  scanf("%d%d",&m,&n);
        memset(dp,0,sizeof(dp));
        dp[0][0][0]=1;
           for(int k=1;k<=m*n;k++)
            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    dp[i][j][k]+=dp[i-1][j-1][k-1]*1.0*(m-i+1)*(n-j+1)/(1.0*(m*n-k+1));
                    dp[i][j][k]+=dp[i-1][j][k-1]*1.0*(m-i+1)*j/(1.0*(m*n-k+1));
                    dp[i][j][k]+=dp[i][j-1][k-1]*1.0*i*(n-j+1)/(1.0*(m*n-k+1));
                    if(i==m&&j==n) continue;
                    dp[i][j][k]+=dp[i][j][k-1]*1.0*(i*j-k+1)/(1.0*(m*n-k+1));
                }
            }
        double ans=0;
        for(int i=0;i<=n*m;i++)
            ans+=dp[m][n][i]*i;
           printf("%.8f\n",ans);
     }
    return 0;
}

或者直接累计不大于k的概率

#include <queue>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
double dp[55][55][3005];
int main(){
     int t;
     int m,n;
     scanf("%d",&t);
     while(t--)
     {  scanf("%d%d",&m,&n);
        memset(dp,0,sizeof(dp));
        dp[1][1][1]=1;
        for(int k=2;k<=n*m;k++){
            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    dp[i][j][k]+=dp[i-1][j-1][k-1]*1.0*(m-i+1)*(n-j+1)/(1.0*(m*n-k+1));
                    dp[i][j][k]+=dp[i-1][j][k-1]*1.0*(m-i+1)*j/(1.0*(m*n-k+1));
                    dp[i][j][k]+=dp[i][j-1][k-1]*1.0*i*(n-j+1)/(1.0*(m*n-k+1));
                    dp[i][j][k]+=dp[i][j][k-1]*1.0*(i*j-k+1)/(1.0*(m*n-k+1));
                }
            }
        }
        double ans=0;
        for(int i=1;i<=n*m;i++)
            ans+=(dp[m][n][i]-dp[m][n][i-1])*i;
           printf("%.12f\n",ans);







     }

    return 0;
}