#BZOJ2362. 二叉树计数
-
ID: 804
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
二叉树计数
No submission language available for this problem.
题目描述
在那个植树节，晚上，小L，小H，小X讨论起了一个关于树的问题：
有多少个不同的二叉树最长链为N。
但是他们发现，答案随N增长的速度太快了，他们想不出什么好方法，便求助于你。
由于答案可能会很大，你只需要输出答案mod 10K后的结果即可。
输入格式
包含两个正整数N，K。表示询问有多少个不同的二叉树最长链为N。
输出格式
包含一个非负整数，为答案mod 10K后的结果。
2 10
7
数据范围与约定
对于100%的数据，有N≤200000，K≤64；
【提示】
关于二叉树：
二叉树的递归定义：二叉树要么为空，要么由根结点，左子树，右子树组成。左子树和右子树分别是一棵二叉树。
请注意，有根树和二叉树的三个主要差别：
1. 树的结点个数至少为1，而二叉树的结点个数可以为0；
2. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
3. 树的结点无左、右之分，而二叉树的结点有左、右之分。
关于最长链：
最长链为这棵二叉树中一条最长的简单路径，即不经过重复结点的一条路径。可以容易证明，二叉树中最长链的起始、结束结点均为叶子结点。