C++(clang++11) 解法, 执行用时: 1880ms, 内存消耗: 163856K, 提交时间: 2021-02-03 19:20:05

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
int n,m;
double f[5005][5005];
bool vis[5005][5005];
double dfs(int num,int x,int y)
{
	if(vis[x][y])return f[x][y];
	if(!num)return x>y;
	vis[x][y]=true;
	double res=0;
	for(int j=1;j<=m;j++){
		if(num%2==0)res=0;
		else res=1;
		for(int i=0,v=num&1?y:x,b=1;i<n;i++,v/=m+1,b*=m+1){
			if(v%(m+1))continue;
			if(num%2==0)res=max(res,dfs(num-1,x+j*b,y));
			else res=min(res,dfs(num-1,x,y+j*b));
		}
		f[x][y]+=res/m;
	}
	return f[x][y];
}
int main()
{
	scanf("%d%d",&n,&m);
	printf("%.7lf\n",dfs(n*2,0,0));
}