推导思路

第一次坐到这种类型的题，社会社会（抱拳）。

先考虑怎么算分母：如果有 \(f_i\) 代表大小为 \(i\) 的树的种类数，那么可以显然得到 \(f_i = \sum_{j = 0}^{n – 1} f_j f_{n – j – 1}\)。得到这一步之后，分治 FFT？不，数据范围到达了惊人的 \(10^9\)，所以分治 FFT 显然不现实。我们可以继续推：

\[ \begin{aligned} F(x) &= 1 + xF^2(x), x \in [0, 1) \\ &= \frac{1 \pm \sqrt{1 – 4x}}{2x} = \frac{1 – \sqrt{1 – 4x}}{2x} \end{aligned} \]

看不出什么，我们继续用广义二项式进行展开：

\[ \begin{aligned} F(x) &= \frac{1 – \sqrt{1 – 4x}}{2x} \\ &= \frac{1 – (1 – 4x)^{\frac{1}{2}}}{2x} = \frac{1 – \sum_{i = 0}^{\infty} (-1)^i {\frac{1}{2} \choose i} (4x)^i}{2x} \\ &= \frac{1}{2x}(1 – \sum_{i = 0}^{\infty} (-4)^i {\frac{1}{2} \choose i} x^i) \\ &= \frac{1}{2x} – \sum_{i = 0}^{\infty} (-4)^i {\frac{1}{2} \choose i} x^{i – 1} = \frac{1}{2x} – (\frac{1}{2x} + \sum_{i = 1}^\infty (-4)^i {\frac{1}{2} \choose i} x^{i – 1}) \\ &= \sum_{i = 0}^\infty (-4)^{i + 1} \frac{\prod_{j = 0}^{i + 1}(\frac{1}{2} + i)}{(i + 1)!} x^{i} \end{aligned} \]

再往下展开就发现系数是卡特兰数，然后就可以直接代公式算就行了。

代码

// P3978.cpp
#include <bits/stdc++.h>

using namespace std;

int n;

int main()
{
    scanf("%d", &n);
    printf("%.10lf\n", 1.0 * n * (n + 1) / double(2.0 * (2.0 * n - 1)));
    return 0;
}