C++14(g++5.4) 解法, 执行用时: 53ms, 内存消耗: 17084K, 提交时间: 2019-12-18 14:36:03

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 2510
using namespace std;
int n,m;
double f[maxn][maxn];
int main()
{
    scanf("%d%d",&n,&m);
    n*=m;
    for(int j=0;j<=n;j++){
        for(int i=0;i<=n;i++){
            if((!i&&!j)||(i>j)||(i+j>n)||((j-i)&1)) continue;
            double p=double(i)/j;
            if(j&&i) f[i][j]+=p*(1+f[i-1][j-1]);
            if(j>=2){
                double b=1.0/(j-1),c=double(j-i-2)/(j-1),d=1-b-c;
                f[i][j]+=(1-p)*(b*(1+f[i][j-2])+c*(1+f[i+2][j-2])+d*(2+f[i][j-2]));
            }
        }
    }
    printf("%.18f",f[0][n]);
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 18ms, 内存消耗: 11384K, 提交时间: 2023-04-14 11:13:57

#include<cstdio>
double dp[2505][2505];
int main()
{
	int n,n_;scanf("%d%d",&n,&n_);(n*=n_)>>=1;
	for(int i=1;i<=n;i++)for(int j=i;j>=0;j--)
	{
		double unno=2*i-j,immatch=2*i-2*j;
		if(j)dp[i][j]=j/unno*(dp[i-1][j-1]+1);//翻了个找到过的牌
		if(unno>1)
		{
			if(i>j)dp[i][j]+=immatch/unno/(unno-1)*(dp[i-1][j]+1);//临时凑到对
			if(immatch>2)dp[i][j]+=immatch/unno*(immatch-2)/(unno-1)*(dp[i][j+2]+1);//翻了两张对不上的牌
			dp[i][j]+=immatch/unno*j/(unno-1)*(dp[i-1][j]+2);//翻了一张对不上的，但找到一对
		}
	}
//	for(int i=0;i<=10;i++,putchar(10))for(int j=0;j<=10;j++)printf("%.3lf",dp[i][j]);
	printf("%.12lf",dp[n][0]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 43ms, 内存消耗: 17100K, 提交时间: 2020-07-16 18:49:07

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
double dp[2501][2501];
int main()
{
	int n,m,o;
	scanf("%d%d",&n,&m);
	o=n*m;
	for(int j=0;j<=o;j++)
	{
		for(int i=0;i<=o;i++)
		{
			if((!i&&!j)||(i>j)||(i+j>o)||((j-i)&1))continue;
			double p=double(i)/j;
			if(j&&i){
				dp[i][j]+=p*(1+dp[i-1][j-1]);
			}
			if(j>=2)
			{
				double b=1./(j-1),c=double(j-i-2)/(j-1),d=1-b-c;
				dp[i][j]+=(1-p)*(b*(1+dp[i][j-2])+c*(1+dp[i+2][j-2])+d*(2+dp[i][j-2]));
			}
		}
	}
	printf("%.11lf",dp[0][o]);
	return 0;
}