记录编号	101296	评测结果	AAAAAAAAAA
题目名称	[SGU U385]高地人游戏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2014-05-11 15:16:25	内存使用	17.11 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=110;
typedef long double LD;
int N;
LD f[SIZEN][SIZEN][SIZEN]={0};
bool visF[SIZEN][SIZEN][SIZEN]={0};
LD G[SIZEN][SIZEN]={0};
bool visG[SIZEN][SIZEN]={0};
LD derange[SIZEN]={0};
LD A[SIZEN][SIZEN]={0};
LD DPF(int i,int j,int k);
LD DPG(int i,int j){//需要确定i,最长环是j
	if(visG[i][j]) return G[i][j];
	visG[i][j]=true;
	LD &ans=G[i][j];
	ans=0;
	for(int k=1;k<=i/j;k++) ans+=DPF(i,j,k);//枚举最长环j出现的次数
	return ans;
}
LD DPF(int i,int j,int k){//已经确定i个数,最长环为j,有k个最长环
	if(visF[i][j][k]) return f[i][j][k];
	visF[i][j][k]=true;
	LD &ans=f[i][j][k];
	ans=0;
	if(k==1){
		if(i==j){
			//单独分出来一个长度为i的环
			//实际上就是选出i个有序序列,前一个连后一个,由于可能会旋转还要除以i
			ans=A[N][i]/(i+0.0);
		}
		else if(2<=j&&j<=i-2){//最长环>=2(也就是合法了),最长环不是i(剩下1明显不合法,因此是i-2)
			//先放上其他的,再确定这个长度为j的最长环
			for(int l=2;l<=min(j-1,i-j);l++){//枚举次长环
				ans+=DPG(i-j,l)*A[N-(i-j)][j]/(j+0.0);//在去掉环的DP基础上,最长环就是N-(i-j)选j
			}
		}
	}
	else{//长度为j的最长环不止一个
		if(2<=j&&j<=i-2&&1<k&&k<=(i/j)){//状态合法
			//我们可以直接去掉一个最长环,调用那个F值
			ans=DPF(i-j,j,k-1)*A[N-(i-j)][j]/(j+0.0)/(k+0.0);
			//在去掉一个环的DP基础上,最长环是N-(i-j)选j,而k个环无论挑哪个去掉都是地位相当的
		}
	}
	return ans;
}
void init(void){
	derange[1]=0,derange[2]=1;
	for(int i=3;i<=N;i++) derange[i]=(i-1)*(derange[i-1]+derange[i-2]);
	for(int i=1;i<=N;i++){
		A[i][1]=i;
		for(int j=2;j<=i;j++) A[i][j]=A[i][j-1]*(i-j+1);
	}
}
void work(void){
	double ans=0;
	for(int j=2;j<=N;j++){
		for(int k=1;k<=N/j;k++){
			ans+=j*k*DPF(N,j,k);
		}
	}
	ans/=derange[N];
	printf("%.10lf\n",ans);
}
int main(){
	freopen("highlander.in","r",stdin);
	freopen("highlander.out","w",stdout);
	scanf("%d",&N);
	init();
	work();
	return 0;
}