#P7201. [2018西部多校]珂学计树题

    ID: 7017 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500省选/NOI-Burnside 引理普通生成函数Lagrange 反演欧拉函数线性筛阶乘逆元预处理约数成对枚举模逆元快速幂

[2018西部多校]珂学计树题

题目描述

考虑有 nn 个结点的有根有序二叉树,左儿子和右儿子有区别。从根结点出发,不断沿右儿子向下,直到到达没有右儿子的结点 vv。如果 vv 不是根结点,可以执行一次操作:断开原根与其右儿子之间的边,让右儿子成为新根,再把原根接为 vv 的右儿子。原根的左子树随原根保留。

如果两棵树可以通过这种操作若干次后变成同构的二叉树,就把它们视为同一种。求 nn 个结点的本质不同二叉树数目。

输入格式

一行一个整数 nn。

输出格式

一行一个整数,表示答案对 998244353998244353 取模的结果。

样例 1

3
4

当 n=3n=3 时,根的左右儿子各为一个结点的树,执行一次操作后得到根只有右儿子、该右儿子只有左儿子的树。这两棵树只计一次。

样例 2

6
80

样例 3

20
451434801

样例 4

900000
255023975

数据范围与约定

1≤n≤1061\le n\le 10^6。各测试点的上界如下。

测试点 nn 的上界
1–2 1010
3–5 100100
6–7 10001000
8 10510^5
9–10 10610^6

所有测试点的 nn 与上述样例不同。

原 PDF 题面