題目描述

輸入

輸入一個正整數N，代表有根樹的結點數

輸出

?輸出這棵樹期望的葉子節點數。要求誤差小于1e-9

樣例輸入

1

樣例輸出

1.000000000

提示

?1<=N<=10^9

?

設$f[n]$表示$n$個節點能形成二叉樹的方案數，$g[n]$表示所有方案的葉子數之和

$ans=\frac{g[n]}{f[n]}$，f$[n]$就是卡特蘭數(這是卡特蘭數的一個應用)

那么$g[n]$怎么求呢？

假設一種$n$節點二叉樹有$k$個葉子，那么$g[n]=\sum k$

我們將這$k$個葉子中任意一個點刪除都能得到一種形態的$n-1$節點二叉樹

那么$g[n]$就是所有$n$節點二叉樹刪除一個節點能得到的$n-1$節點二叉樹的方案數之和

這樣還是求不了啊？

我們反過來看，將$g[n]$看成是$n-1$節點二叉樹加一個節點能形成$n$節點二叉樹的方案數之和

考慮對于一種形態的$n-1$節點二叉樹，每個點能向下連出兩條邊(連向左兒子和右兒子的邊)，$n-1$個節點就有$2n-2$條邊

因為將這$n-1$個點連成一棵樹已經占用了$n-2$條邊，所以還有$n$條邊的下端是空閑的，在這$n$條邊下端任意一個位置加一個點都能形成一種形態的$n$節點二叉樹

每種形態$n-1$節點二叉樹都能形成$n$種$n$節點二叉樹，共$f[n-1]$種形態，因此$g[n]=n*f[n-1]$

$f[n]=C_{2n}^{n}-C_{2n}^{n-1}=\frac{(2n)!}{n!(n+1)!}$，$ans=\frac{g[n]}{f[n]}=\frac{n*(n+1)}{2(2n-1)}$

#include<set> #include<map> #include<queue> #include<cmath> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int n; double ans; int main() {scanf("%d",&n);ans=1.0*n*(n+1)/2;ans/=(2.0*n-1);printf("%.9lf",ans); }

轉載于:https://www.cnblogs.com/Khada-Jhin/p/9833479.html

總結

以上是生活随笔為你收集整理的BZOJ4001[TJOI2015]概率论——卡特兰数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。