时间限制:

5000ms

单点时限:

1000ms

内存限制:

256MB

描述

大家对斐波那契数列想必都很熟悉:

a₀ = 1, a₁ = 1, a_i = a_i-1 + a_i-2,(i > 1)。

现在考虑如下生成的斐波那契数列:

a₀ = 1, a_i = a_j + a_k, i > 0, j, k从[0, i-1]的整数中随机选出（j和k独立）。

现在给定n，要求求出E(a_n)，即各种可能的a数列中a_n的期望值。

输入

一行一个整数n，表示第n项。(1<=n<=500)

输出

一行一个实数，表示答案。你的输出和答案的绝对或者相对误差小于10^-6时被视为正确答案。

样例解释

共存在3种可能的数列

1,2,2  1/4

1,2,3  1/2

1,2,4  1/4

所以期望为3。

 

样例输入

2

样例输出

3.000000

 

设f(n)表示an的期望值。

那么

设s(n)表示f(n)前n项的和，那么

当时Hihocoder挑战赛时没高兴推，直接暴力打表过的。

代码：

#include 
     
      #include 
      
       #define LL long longusing namespace std;double e[505];LL Sum(int n){    LL ans = 0;    for (int i = 0; i < n; ++i)    {        for (int j = 0; j < n; ++j)        {            ans += e[i]+e[j];        }    }    return ans;}void Init(){    e[0] = 1;    double C2;    for (int i = 1; i <= 500; ++i)    {        C2 = i*i;        e[i] = Sum(i) / C2;    }}int main(){    Init();    int n;    while (scanf("%d", &n) != EOF)    {        printf("%.7lf\n", e[n]);    }    return 0;}