题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=385
题意:
思路:
double f[N][N][N],g[N][N],A[N][N]; int n; void init() { int i,j; for(i=2;i<=100;i++) { A[i][1]=i; for(j=2;j<=i;j++) A[i][j]=A[i][j-1]*(i+1-j); } } double DFS(int,int,int); double dfs(int i,int j) { if(g[i][j]>=0) return g[i][j]; if(j>i) return 0; int k; g[i][j]=0; for(k=1;k*j<=i;k++) g[i][j]+=DFS(i,j,k); return g[i][j]; } double DFS(int i,int j,int k) { if(f[i][j][k]>=0) return f[i][j][k]; if(i<=1||j<=1||k<=0||k*j>i||i<j) return 0; if(i==j&&k==1) return A[n][i]/i; f[i][j][k]=DFS(i-j,j,k-1)*A[n-i+j][j]/j/k; if(k==1) { int t,L=min(j-1,i-j); double temp=A[n-i+j][j]/j; for(t=2;t<=L;t++) f[i][j][k]+=dfs(i-j,t)*temp; } return f[i][j][k]; } int main() { init(); Rush(n) { clr(f,-1); clr(g,-1); double s1=0,s2=0; int j,k; for(j=2;j<=n;j++) for(k=1;k<=n;k++) { s1+=j*k*DFS(n,j,k); s2+=DFS(n,j,k); } double ans=s1/s2; printf("%.10lf\n",ans); } }