记录编号	232543	评测结果	AAAAAAAAAA
题目名称	[SGU U385]高地人游戏	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.057 s
提交时间	2016-03-01 21:05:38	内存使用	15.82 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
typedef long double LD;
const int SIZEN=110;
const double zero=1e-7;
LD d[SIZEN];
LD A[SIZEN][SIZEN]={0};
LD f[SIZEN][SIZEN][SIZEN]={0};
LD g[SIZEN][SIZEN]={0};
int N;
void prepare()
{
	d[1]=0,d[2]=1;
	for(int i=3;i<=N;i++) d[i]=(i-1)*(d[i-1]+d[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);
	}
}
LD getf(int i,int j,int k);
LD getg(int i,int j)
{
	if(g[i][j]>zero) return g[i][j];
	for(int k=1;k<=i/j;k++) g[i][j]+=getf(i,j,k);
	return g[i][j];
}
LD getf(int i,int j,int k)
{
	if(f[i][j][k]>zero) return f[i][j][k];
	//cout<<i<<" "<<j<<" "<<k<<" "<<A[N][j]/(j+0.0)<<endl;
	if(i==j&&k==1) f[i][j][k]=A[N][j]/(j+0.0);
	else if(2<=j&&j<=i-2&&1<k&&k<=i/j) f[i][j][k]=(getf(i-j,j,k-1)*A[N-i+j][j]/(j+0.0))/(k+0.0);
	else if(2<=j&&j<=i-2&&k==1) 
	{
		for(int p=2;p<=min(j-1,i-j);p++) f[i][j][k]+=getg(i-j,p)*A[N-i+j][j]/(j+0.0);
	}
	else f[i][j][k]=0;
	return f[i][j][k];
}
void work()
{
	double ans=0;
	for(int j=2;j<=N;j++) 
		for(int k=1;k<=N/j;k++) 
		{
			ans+=k*j*getf(N,j,k);
		}
	ans/=d[N];
	printf("%.10lf\n",ans);
}
int main()
{
	freopen("highlander.in","r",stdin);
	freopen("highlander.out","w",stdout);
	scanf("%d",&N);
	prepare();
	work();
	return 0;
}