题意：

给N×M的棋盘。每天随机找一个没放过棋子的格子放一个棋子

问使得每一个每列都有棋子的天数期望

思路：

dp[i][j][k] 代表放了i个棋子占了j行k列 到达目标状态的期望

然后从 dp[n*m][n][m] 往后递推就好了。

由于知道了有i个棋子 比如一个状态dp[6][3][3]

x x x o o o

x o o o o o

x o x o o o

o o o o o o

对于 dp[i+1][3][3] 事实上就是3*3剩下的空再放一个，概率就是(j*k-i) / (n*m-i)

对于 dp[i+1][4][3] 就是剩下的行乘上现有的列找一个放，概率就是  ((n-j)*k)/(n*m-i)

对于 dp[i+1][3][4]就是剩下的列乘上现有的行找一个放 。概率就是 ((m-k)*j)/(n*m-i)

最后 dp[i+1][4][4] 就是剩下的行乘上剩下的列找一个放 ，概率就是(n-j)*(m-k))/(n*m-i)

然后期望是一天加上就好了。

注意一下几个非法的情况就好了

然后能够用滚动数组优化空间。

代码：

#include"cstdlib"

#include"cstdio"

#include"cstring"

#include"cmath"

#include"queue"

#include"algorithm"

#include"iostream"

#include"map"

#include"string"

using namespace std;

double dp[2][55][55];

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        int i,j,k;

        memset(dp,0,sizeof(dp));

        for(i=n*m;i>=0;i--)

        {

            for(j=n;j>=0;j--)

            {

                for(k=m;k>=0;k--)

                {

                    if(j==n&&k==m) continue; //终于状态  期望是0

                    if(i>j*k) continue;  //棋子多了 非法

                    double tep=0;  //以下的注意不能等于0

                    if(j>0&&k>0) tep+=(dp[1-(i+1)%2][j][k]+1)*((j*k-i)/(n*m-i*1.0));

                    if(k>0) tep+=(dp[1-(i+1)%2][j+1][k]+1)*(((n-j)*k)/(n*m-i*1.0));

                    if(j>0) tep+=(dp[1-(i+1)%2][j][k+1]+1)*(((m-k)*j)/(n*m-i*1.0));

                    tep+=(dp[1-(i+1)%2][j+1][k+1]+1)*((n-j)*(m-k))/(n*m-i*1.0);

                    dp[1-(i)%2][j][k]=tep;

                }

            }

        }

        printf("%.12f\n",dp[1-(0)%2][0][0]);

    }

    return 0;

}