「TJOI2015」概率论 解题报告

「TJOI2015」概率论

令(f_i)代表(i)个点树形态数量，(g_i)代表(i)个点叶子个数

然后列一个dp

[f_i=sum_{j=0}^{i-1} f_j f_{i-j-1}\ g_i=2sum_{j=0}^{i-1} f_j g_{i-j-1} ]

然后显然可以卷，但没有1e5的部分分

然后打表

[frac{1}{1} frac{3}{3} frac{6}{5} frac{10}{7} frac{15}{9}... ]

然后猜到通项是

[frac{n*(n-1)/2}{n*2-1} ]

上面是乱搞做法

正解是卡特兰数，生成函数之类的一些东西，留坑待填

话说如果没看出来卡特兰数放在18年是不是就凉了啊...

---

Code:

#include <cstdio>
double n;
int main()
{
    scanf("%lf",&n);
    double a=(1+n)*n/2,b=n*2-1,ans=a/b;
    printf("%.9lf
",ans);
    return 0;
}

---

2019.2.25