Description
Input
输入一个正整数N,代表有根树的结点数
Output
输出这棵树期望的叶子节点数。要求误差小于1e-9
Sample Input
1
Sample Output
1.000000000
HINT
1<=N<=10^9
solution
神仙题,(思维难度适中,码量极低,解法自然)
设(a_n)为(n)个节点的二叉树的个数,(b_n)为(n)个节点二叉树所有方案的叶子节点数之和,那么答案显然为(a_n/b_n)。
那么枚举左右子树有多少节点显然可以得到:
[a_n=sum_{i=0}^{n-1}a_ia_{n-i-1}
]
(众所周知)这就是卡特兰数,即:
[a_n=frac{1}{n-1}inom{2n}{n}
]
对于(b_n),同样枚举左右子树节点个数可得:
[b_n=sum_{i=0}^{n-1}a_i*b_{n-i-1}+b_{i}*a_{n-i-1}
]
即
[b_n=2sum_{i=0}^{n-1}a_ib_{n-i-1}
]
然后考虑这两个函数的生成函数,设:
[F(x)=sum_{i=0}^{infty}a_ix^i\
G(x)=sum_{i=0}^{infty}b_ix^i\
]
然后注意到上面关于(a)的式子是一个卷积形式,构造生成函数的乘积:
[F^2(x)=sum_{p=0}^infty sum_{i=0}^{p}a_ia_{p-i}x^p
]
乘(x)右移:
[egin{align}
&~~~~~xF^2(x)\&=sum_{p=1}^infty sum_{i=0}^{p-1}a_ia_{p-i-1}x^p
\&=sum_{p=1}^infty a_px^p
end{align}
]
补上第0项,得:
[F(x)=xF^2(x)+1
]
对于(F(x)),解方程得:
[F(x)=frac{1pm sqrt{1-4x}}{2x}
]
对于取正号时:
[lim_{x
ightarrow0}F(x)=infty
]
函数不收敛,舍去。
取负号时:
[lim_{x
ightarrow0}F(x)=1
]
所以
[F(x)=frac{1- sqrt{1-4x}}{2x}
]
同样,对于(b_n),也是一个卷积形式,得:
[egin{align}
&~~~~~2xG(x)F(x)\&=sum_{p=1}^infty 2sum_{i=0}^{p-1}a_ib_{p-i-1}x^p\
&=sum_{p=2}^infty b_px^p
end{align}
]
注意这里(p=1)时后面的卷积为0,所以补上一个(x)得:
[G(x)=2xF(x)G(x)+x
]
解得:
[G(x)=frac{x}{sqrt{1-4x}}
]
然后注意到:
[(F(x)*x)^prime=frac{1}{sqrt{1-4x}}=frac{G(x)}{x}
]
对于((F(x)*x)^prime),第(n)项为:
[a_nx^n
ightarrow a^nx^{n+1}
ightarrow (n+1)a^nx^n
]
对于(G(x)/x),第(n+1)项为:
[b_{n+1}x^{n+1}
ightarrow b_{n+1}x^n
]
所以比较系数可得:
[(n+1)a^nx^n=b_{n+1}x^n
]
即:
[na_{n-1}=b_n
]
考虑到
[a_n=frac{1}{n+1}inom{2n}{n}
]
所以答案为:
[frac{b_n}{a_n}=frac{na_{n-1}}{a_n}=frac{n(n+1)}{2(2n-1)}
]
代码....读入输出小清新题
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
int main() {
int n;read(n);
printf("%.9lf
",(double)n*(n+1)/2/(2*n-1));
return 0;
}