P3978 概率论

膜拜 wck

---

做法

考虑一个经典问题：n个点的二叉树数量是多少。考虑转括号序，一个节点是一个括号，左子树放在括号内，右子树放在括号右侧。可得 \(n\) 个点二叉树数量为 \(Cat_n\)。

我们注意到叶子在括号序上形如 \(())\) 或在序列末尾的 \(()\)，考虑拆贡献，计算括号序上一个位置能加叶子的长 \(2(n-1)\) 的括号序的方案数，答案即为方案数求和除以总方案数。再拆一次贡献，方案数求和可以变为对每一个长 \(2(n-1)\) 的括号序计算能加叶子的位置数，因为每一个 \()\) 和末尾能加叶子，因此位置数恒为 \(n\)。因此答案为 \(\frac{n\cdot Cat_{n-1}}{Cat_n}=\frac{n\cdot\frac{(2n-2)!}{(n-1)!n!}}{\frac{(2n)!}{n!(n+1)!}}=\frac{n(n+1)}{2(2n-1)}\)。

另一种角度

考虑在 \(n-1\) 个点的树上加一个叶子，设有两个儿子的点数为 \(a\)，一个儿子的点数为 \(b\)，叶节点数为 \(c\)，则加叶子方案为 \(b+2c\)，根据 \(a+b+c=n-1\) 和 \(2a+b=n-2\) 可得 \(b+2c=2(n-1)-(n-2)=n\)。\(n\) 个点数的叶子总数等于 \(n-1\) 个点二叉树数量乘以 \(n\)，即 \(n\cdot Cat_{n-1}\)。

code

#include<bits/stdc++.h>
using namespace std;
long long n;
int main(){scanf("%lld",&n);printf("%.9Lf\n",(long double)n/(4*n-2)*(n+1));return 0;
}