首页 > 代码库 > [BZOJ1089][SCOI2003]严格n元树(递推+高精度)
[BZOJ1089][SCOI2003]严格n元树(递推+高精度)
题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1089
分析:
第一感觉可以用一个通式求出来,但是考虑一下很麻烦,不好搞的。很容易发现最底层必有一个是满高度的,其他的任意。
所以直接的递推也不好想。
(以下所述都是n元树)
于是可以令f[d]为深度<=d的树的个数,那么深度为d的就是f[d]-f[d-1]
对于深度<=d的又该怎么处理呢?
考虑第一层的n个点(根为0层),每个点都要底下连子树,深度为0~i-1,方案数即f[d-1],而且这n个点互不影响
所以f[d]=f[d-1]^n+1(注意这个要加1,即只有一个根节点的情况)
然后注意高精度就可以了。
[BZOJ1089][SCOI2003]严格n元树(递推+高精度)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。