Chieh's Blog

Because Of Coding

ZOJ Problem Set - 3822 Domination

Chieh posted @ 2015年8月21日 21:30 in NO Answer No Speak , 330 阅读
/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=5*12;
double  ai[maxn*maxn][maxn][maxn];
int T,n,m;
double ans;
void init()
{
    ans=0;
    scanf("%d%d",&n,&m);
    ai[0][0][0]=1;
    double  p=n*m;
    for(int k=1; k<=n*m; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                ai[k][i][j]=0;
                ai[k][i][j]+=i*j*ai[k-1][i-1][j]/p;
                ai[k][i][j]+=j*i*ai[k-1][i][j-1]/p;
                ai[k][i][j]+=i*j*ai[k-1][i-1][j-1]/p;
                if((i!=n||j!=m)&&i*j>=k)
                {
                    ai[k][i][j]+=ai[k-1][i][j]*(i*j-k+1)/p;
                }
            }
        }
        p--;
    }
}
void play()
{

    double ans=0;
    for(int i=1; i<=n*m; i++)
    {
        ans+=ai[i][n][m]*i;
    }
    printf("%.10f\n",ans);
}

int main()
{

    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter