注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ4001][TJOI2015]概率论  

2015-04-28 18:36:47|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4001: [TJOI2015]概率论

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 209  Solved: 83
[Submit][Status][Discuss]

Description

Input

输入一个正整数N,代表有根树的结点数

Output

 输出这棵树期望的叶子节点数。要求误差小于1e-9

Sample Input

1

Sample Output

1.000000000

HINT

 1<=N<=10^9

Solution

开始的时候式子推错了Wa了好几发= =

n个点所构成的二叉树总共有H[n]种,其中H[n]表示卡特兰数。

考虑在所有方案下的叶子总数,记为f[i]。有fi=2Σ(f[j]*H[i-1-j])

f[n]/H[n]即为答案

打表吧~

1/1 1/1 10/7 5/3 21/11 28/13 12/5 45/17 ...

除开前两项把分母弄成2x+1

分子就是10 15 21 28 36 45 ...

就是长成n*(n-1)/2这样子的。

然后推一推就会出来ans=n*(n+1)/2/(2*n-1),正好满足前两项~

--------------------

试着证明一下:把f拿去写成母函数,会变成f=x/sqrt(1-4x),然后 广义二项式定理 暴力泰勒展开,好像没什么规律。。。

其实 oeis或者 根据上面的结论发现通项为C(2n,n),然后就可以搞了。

//其实x/sqrt(1-4x)=x*O(diff(卡特兰数))真是233

Code

/**************************************************************
    Problem: 4001
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:804 kb
****************************************************************/
 
#include<cstdio>
double n;main(){
    scanf("%lf",&n);printf("%.9lf",n*(n+1)/2/(2*n-1));
}

  评论这张
 
阅读(134)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018