史上最短黑题

看起来一脸懵逼，没有取模，1e-9

根据期望定义，发现

分母是一个卡特兰数，，，，不能直接算

所以考虑怎么消掉一些东西

gn表示n个点的叶子个数和，fn表示n个点二叉树个数

 

结论：g(n)=n*f(n-1)

考虑每个n个点的树的叶子，分别拔掉所有k个叶子，给剩下的k个(n-1)个点的树打上标记

那么，g(n)就是n-1个点的所有的树被打的标记之和

一个n-1个点的树，有n个位置可以有叶子，恰好会被打n次标记！

 

然后，ans(n)=g(n)/f(n)，f(n)=C(2n,n)/(n+1)化简即可。

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')using namespace std;typedef long long ll;template
      
       il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
       
        il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
        
         il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
         
          il void prt(T a[],int st,int nd){
   for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{int main(){    double n;cin>>n;    printf("%.12lf",n*(n+1)/(2*(2*n-1)));    return 0;}}signed main(){    Miracle::main();    return 0;}/*   Author: *Miracle*   Date: 2019/4/23 14:29:28*/