luoguP3978 [TJOI2015]概率论 卡特兰数
考虑分别求出$f_n, g_n$表示$n$个点的有根二叉树的数量和$n$个点的所有情况下有根二叉树的叶子结点的总数
有$f_n = sum_{k} f_k * f_{n - 1 - k}$，因此有$f_n = C_n$，其中$C_n$为卡特兰数
有$g_n = sum_{k} g_k * f_{n - 1 - k} + g_{n - 1 - k} * f_k$
通过打表，可以发现$g_n = n * C_{n - 1}$，可以用归纳法证明
因此答案为$frac{g_n}{f_n} = frac{n * C_{n - 1}}{C_n} = frac{n * (n + 1)}{4 * n - 2}$
复杂度$O(1)$
#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define de long double de n; int main() { cin >> n; de p = (de)n * (de)(n + 1) / (de)(4 * n - 2.0); printf("%.13Lf", p); return 0; }