fork(1) download 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iomanip>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. const int N=205;
  8. int n;
  9. long double Fac[N];
  10. long double C[N][N];
  11. long double P[N][N];
  12. long double F[N][N][N];
  13. long double G[N][N];
  14. long double d[N];
  15.  
  16. void predo(){
  17. 	d[1]=0; d[2]=1;
  18. 	for (int i=3;i<=n;i++) d[i]=(i-1)*(d[i-2]+d[i-1]);
  19. 	memset(C,0,sizeof(C));
  20. 	C[0][0]=1;
  21. 	for (int i=1;i<=n;i++)
  22. 		for (int j=0;j<=i;j++){
  23. 			if (j) C[i][j]+=C[i-1][j-1];
  24. 			C[i][j]+=C[i-1][j];
  25. 		}
  26. 	Fac[0]=1;
  27. 	for (int i=1;i<=n;i++) Fac[i]=Fac[i-1]*i;
  28. 	for (int i=0;i<=n;i++)
  29. 		for (int j=0;j<=i;j++)
  30. 			P[i][j]=C[i][j]*Fac[j];
  31. }
  32.  
  33.  
  34. int main(){
  35. 	scanf("%d",&n);
  36. 	predo();
  37. 	memset(F,0,sizeof(F));
  38. 	memset(G,0,sizeof(G));
  39. 	F[0][0][0]=1;
  40. 	G[0][0]=1;
  41. 	for (int i=1;i<=n;i++) G[0][i]=1;
  42. 	for (int i=2;i<=n;i++){
  43. 		for (int j=2;j<=i;j++)
  44. 			for (int k=1;j*k<=i;k++){
  45. 				if (k==1)
  46. 					F[i][j][k]=G[i-j][j-1]*P[n-i+j][j]/j;
  47. 				else
  48. 					F[i][j][k]=F[i-j][j][k-1]*P[n-i+j][j]/j/k;
  49. //				printf("%d %d %d %lf\n",i,j,k,F[i][j][k]);
  50. 			}
  51. 		for (int j=2;j<=n;j++){
  52. 			G[i][j]=G[i][j-1];
  53. 			for (int k=1;j*k<=i;k++)
  54. 				G[i][j]+=F[i][j][k];
  55. 		}
  56. 	}
  57. 	long double ret=0;
  58. 	for (int j=2;j<=n;j++)
  59. 		for (int k=1;j*k<=n;k++)
  60. 			ret+=F[n][j][k]*j*k;
  61. //	cout << d[4] << endl;
  62. 	cout << fixed << setprecision(14) << ret/d[n] << endl;
  63. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/lIAQX
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!