#P7201. [2018西部多校]珂学计树题
[2018西部多校]珂学计树题
题目描述
考虑有 个结点的有根有序二叉树,左儿子和右儿子有区别。从根结点出发,不断沿右儿子向下,直到到达没有右儿子的结点 。如果 不是根结点,可以执行一次操作:断开原根与其右儿子之间的边,让右儿子成为新根,再把原根接为 的右儿子。原根的左子树随原根保留。
如果两棵树可以通过这种操作若干次后变成同构的二叉树,就把它们视为同一种。求 个结点的本质不同二叉树数目。
输入格式
一行一个整数 。
输出格式
一行一个整数,表示答案对 取模的结果。
样例 1
3
4
当 时,根的左右儿子各为一个结点的树,执行一次操作后得到根只有右儿子、该右儿子只有左儿子的树。这两棵树只计一次。
样例 2
6
80
样例 3
20
451434801
样例 4
900000
255023975
数据范围与约定
。各测试点的上界如下。
| 测试点 | 的上界 |
|---|---|
| 1–2 | |
| 3–5 | |
| 6–7 | |
| 8 | |
| 9–10 |
所有测试点的 与上述样例不同。