C++(g++ 7.5.0) 解法, 执行用时: 39ms, 内存消耗: 16976K, 提交时间: 2022-10-03 13:20:15

#include<bits/stdc++.h>
using namespace std;
const int N=205;
double p[N],f[N][N][N];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)p[i]=i*1.0/n;
    for(int k=n;k>=0;k--){
        for(int j=0;j<=n;j++){
            for(int i=n;i>=0;i--){
                int x=n-i*2-j-k;
                if(x<0)continue;
                double q=1,s=0;
                if(i>1)s+=p[i*2]*p[(i-1)*2]*f[i-2][j+2][k+2],q-=p[i*2]*p[(i-1)*2];
                if(j>1)s+=p[j]*p[j-1]*f[i][j-2][k+2],q-=p[j]*p[j-1];
                if(i&&j)s+=p[i*2]*p[j]*2*f[i-1][j][k+2],q-=p[i*2]*p[j]*2;
                if(x&&i)s+=p[x]*p[i*2]*2*f[i-1][j+2][k+1],q-=p[x]*p[i*2]*2;
                if(x&&j)s+=p[x]*p[j]*2*f[i][j][k+1],q-=p[x]*p[j]*2;
                if(x>1)s+=p[x]*p[x-1]*f[i+1][j][k],q-=p[x]*p[x-1];
                if(q<1)f[i][j][k]=(s+1)/(1-q);
                else f[i][j][k]=0;
            }
        }
    }
    cout << fixed << setprecision(9) << f[0][0][0]<< endl;
}

C++(clang++ 11.0.1) 解法, 执行用时: 29ms, 内存消耗: 32804K, 提交时间: 2022-10-01 20:56:44

#include <bits/stdc++.h>
using namespace std;

const int N = 201;
double dp[N][N][N];//0次参与的个数 1次参与的人数 1次参与且不冲突人数=期望次数

int main()
{
	//freopen("a.txt", "r", stdin);
	int n;
	scanf("%d",&n);
	dp[0][2][0]=dp[0][0][0]=dp[1][0][0]=0;
	for (int i=0;i<=n;i++)
	{
		for (int j=0;j<=n-i;j+=2)
		{
			for (int k=0;k<=j;k+=2)
			{
				double t=0,sum=0;
				if (i>=2)
				{
					sum+=i*(i-1)*dp[i-2][j+2][k];t+=i*(i-1);
				}
				if (i>=1)
				{
					sum+=2*i*(j-k)*dp[i-1][j][k+2];t+=2*i*(j-k);

					sum+=2*i*k*dp[i-1][j][k];t+=2*i*k;
				}
				if (j>=2&&k>=2)
				{
					sum+=k*(k-1)*dp[i][j-2][k-2];t+=k*(k-1);
				}
				if (j>=2)
				{
					sum+=(j-k)*(j-k-2)*dp[i][j-2][k+2];t+=(j-k)*(j-k-2);

					sum+=2*(j-k)*k*dp[i][j-2][k];t+=2*(j-k)*k;
				}
				if (t==0)dp[i][j][k]=0;
				else dp[i][j][k]=(sum+n*n)/t;
			}
		}
	}
	printf("%.9f\n",dp[n][0][0]);
	return 0;
}