102227: [AtCoder]ABC222 H - Beautiful Binary Tree
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Score : $600$ points
Problem Statement
For a positive integer $N$, a rooted binary tree that satisfies the following conditions is said to be a beautiful binary tree of degree $N$.
- Each vertex has $0$ or $1$ written on it.
- Each vertex that is a leaf has $1$ written on it.
- It is possible to do the following operation at most $N-1$ times so that the root has $N$ written on it and the other vertices have $0$ written on them.
- Choose vertices $u$ and $v$, where $v$ must be a child of $u$ or a child of "a child of $u$." Let $a_u \gets a_u + a_v, a_v \gets 0$, where $a_u$ and $a_v$ are the numbers written on $u$ and $v$, respectively.
Given $N$, find the number, modulo $998244353$, of beautiful binary trees of degree $N$.
Constraints
- $1 \leq N \leq 10^7$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$
Output
Print the answer.
Sample Input 1
1
Sample Output 1
1
The only binary tree that satisfies the condition is a tree with one vertex whose root has $1$ written on it.
Sample Input 2
2
Sample Output 2
6
The binary trees that satisfy the condition are the six trees shown below.
Sample Input 3
222
Sample Output 3
987355927
Sample Input 4
222222
Sample Output 4
675337738
Input
题意翻译
对于一个正整数 $n$,我们称满足以下条件的有根二叉树是一棵美丽的 $n$ 阶二叉树。 - 每个节点有一个数字 $0$ 或 $1$,节点 $i$ 的数字记为 $a_i$。 - 每个叶子节点的数字定是 $1$。 - 可以通过进行如下的操作至多 $n - 1$ 次,使得最终根节点上的数字为 $n$,其余节点的数字是 $0$。 - 选择两个节点 $u, v$,其中 $u$ 需要是 $v$ 的父节点或父节点的父节点。作赋值 $a_u\leftarrow a_u + a_v, a_v\leftarrow 0$。 给定 $n$,请计算美丽的 $n$ 阶二叉树的数量。答案对 $998244353$ 取模。 $n \le 10^7$。Output
分数:600分
问题描述
对于正整数$N$,满足以下条件的根为二叉树被称为 度为$N$的美丽二叉树。
- 每个顶点上都写有$0$或$1$。
- 每个叶顶点上都写有$1$。
- 通过以下操作最多进行$N-1$次,使得根顶点上写有$N$,其他顶点上写有$0$。
- 选择顶点$u$和$v$,其中$v$必须是$u$的子顶点或“$u$的子顶点的子顶点”。将$u$和$v$上的数字分别更新为$a_u \gets a_u + a_v, a_v \gets 0$,其中$a_u$和$a_v$分别是$u$和$v$上的数字。
给定$N$,求度为$N$的美丽二叉树的数量,对$998244353$取模。
约束
- $1 \leq N \leq 10^7$
- 输入中的所有值都是整数。
输入
从标准输入按照以下格式给出输入:
$N$
输出
打印答案。
样例输入1
1
样例输出1
1
满足条件的唯一二叉树是一棵只有一个顶点的树,其根顶点上写有$1$。
样例输入2
2
样例输出2
6
满足条件的二叉树是下图所示的六棵树。
样例输入3
222
样例输出3
987355927
样例输入4
222222
样例输出4
675337738