Tom and Jerry got lost in a desert. But they are not bored or afraid at all, because they found a truly interesting thing to do: researching the varied kinds of kakti in the desert!
After careful observations, they found that a kaktus can be seen as a graph consisting of several nodes. To be precise, an nn-node kaktus is an undirected connected graph that has only 11 node as the root, in which every edge belongs to exactly one simple cycle and all nodes are unlabelled. You can refer to sample case for a better understanding.
Finding something new is always exciting, but it brings them new doubts.
"How many different kinds of nn-node kakti are there?" wondered Tom.
"Your problem is simpler than mine. I am wondering how many different kinds of 1,2,3,..,n1,2,3,..,n-node kakti there are." said Jerry.
2967: Desert
| Time Limit | $12$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $3$ | 正确数量 | $2$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
Description
Input
One line containing a number nn (1≤n≤1051≤n≤105).
Output
nn lines, each line containing a number, the number of nn-node kakti.
As these numbers can be very large, output them modulo 998244353998244353.
As these numbers can be very large, output them modulo 998244353998244353.
Sample Input复制
4
Sample Output复制
1
1
3
8
提示
Here are the 8 4-node kakti.
推荐代码 查看2967 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$3865 $ms] | 淡意的温柔 | 605340 | 2020-07-03 14:59:19 |
| 内存最少[$10368 $KB] | 刘成健 | 460913 | 2019-09-04 20:45:02 |
| 第一AC | 刘成健 | 460913 | 2019-09-04 20:45:02 |
| 第一挑战 | 刘成健 | 460912 | 2019-09-04 20:41:01 |
赛题来源/所属竞赛 2019 Multi-University Training Contest 1 N/A
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|