Endless Spin

Question

Problem Description

I spin it again and again,and throw it away finally.
So now I have a row of n ball,named from 1 to n,each ball is white initially.
At each step I randomly chose a interval [l, r] and paint all ball in this interval to black.
It means every interval have a equal chance of being chosen.
And I'll stop if all ball are black.What is the expected steps before I stop?

Input
The first line contains integer T(1<=T<=50). Denoting the number of the test cases.
Then T lines follows, each line contains an integer n (1<=n<=50).

Output
For each test cases,print the answer in a line.
Print the answer rounded to 15 decimal places.

Sample Input
3
1
2
3

Sample Output
1.000000000000000
2.000000000000000
2.900000000000000

Answer 1

#include
#include
#include
#include
#define G(x) (((x+1)*(x))>>1)
#define ll long long
using namespace std;
int n;
ll f[55][2555][2];
int main()
{
int ca;
scanf("%d",&ca);
while(ca--)
{
scanf("%d",&n);
memset(f,0,sizeof(f));
f[0][0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
for(int s=G(i-j-1);s<=G(i);s++)
for(int b=0;b<=1;b++)
f[i][s][b]+=f[j][s-G(i-j-1)][b^1];

double ans=0,tot=G(n);
for(int i=1;i<=n;i++)
for(int s=0;s<=G(i);s++)
if(f[i][s][1]-f[i][s][0]!=0)
ans+=tot*(f[i][s][1]-f[i][s][0])/(tot-s-G(n-i));
printf("%.15lf\n",ans);

}
return 0;
}