80求助卡常
查看原帖
80求助卡常
135258
charm1楼主2021/7/30 10:38

RT

#include <bits/stdc++.h>
#define double __float128
using namespace std;
const int maxn=105;
const int maxm=10205;
const double eps=(1e-31);
int n,m;
signed t;
double dp[2][maxn][maxm][3];
inline int read(){
	int ret=0,f=1;	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void write(double x){
	if(x+eps>1){
		printf("1.");
		for(int k=1;k<=t;k++) putchar('0');
		puts("");
		return;
	}
	int now=0;
	printf("0.");
	for(int k=1;k<=t;k++){
	    x=(x-now*1.0)*10.0;
	    if(k==t)x=x+0.5;
	    now=x;printf("%d",now);
	}
	puts("");
}
signed main(){
	n=read();   m=read();   t=read();
	dp[0][0][0][0]=1;
	bool now=0;
	for(register int k=0;k<n;k++){
		now=!now;
		memset(dp[now],0,sizeof(dp[now]));
		for(register int j=0;j<=k;j++)
		for(register int i=0;i<=min((n*k<<1),n*n);i++){
			int d;
			d=0;
			if(dp[!now][j][i][d]>eps){
				double x=dp[!now][j][i][d]/(k+1);
				int w=n-k-1;
				dp[now][j][i][d]+=x*((j<<1)-d);
				if(j+1-d>=0)	dp[now][j+1][i+(w<<1)][d]+=x*(j+1-d);
				if(i>=(w<<1)&&j) dp[now][j-1][i-(w<<1)][d]+=x*(j-1);
				if(d<2){
					if(i>=w&&j)	dp[now][j][i-w][d+1]+=x*(2-d);
					dp[now][j+1][i+w][d+1]+=x*(2-d);
				}
			}
			d=1;
			if(dp[!now][j][i][d]>eps){
				double x=dp[!now][j][i][d]/(k+1);
				int w=n-k-1;
				dp[now][j][i][d]+=x*((j<<1)-d);
				if(j+1-d>=0)	dp[now][j+1][i+(w<<1)][d]+=x*(j+1-d);
				if(i>=(w<<1)&&j) dp[now][j-1][i-(w<<1)][d]+=x*(j-1);
				if(d<2){
					if(i>=w&&j)	dp[now][j][i-w][d+1]+=x*(2-d);
					dp[now][j+1][i+w][d+1]+=x*(2-d);
				}
			}
			d=2;
			if(dp[!now][j][i][d]>eps){
				double x=dp[!now][j][i][d]/(k+1);
				int w=n-k-1;
				dp[now][j][i][d]+=x*((j<<1)-d);
				if(j+1-d>=0)	dp[now][j+1][i+(w<<1)][d]+=x*(j+1-d);
				if(i>=(w<<1)&&j) dp[now][j-1][i-(w<<1)][d]+=x*(j-1);
				if(d<2){
					if(i>=w&&j)	dp[now][j][i-w][d+1]+=x*(2-d);
					dp[now][j+1][i+w][d+1]+=x*(2-d);
				}
			}
		}

//		if(k==0) cout<<dp[1][2][1]<<endl;
	}
	double ans=0;
	for(int k=m;k<=n*n;k++)
	ans+=dp[now][1][k][2];
//	for(int k=0;k<=n*n;k++) cout<<k<<" ",write(dp[1][k][2]);
//	double now=0;
//	for(int k=0;k<=n*n;k++) cout<<k<<" ",write(now+=dp[1][k][2]);
	write(ans);
	return 0;
}

2021/7/30 10:38
加载中...