#2411. 树
树
树
题目描述
ZJOI 2022 第一试 树(tree) 树(tree) 【题目背景】 一年一度的ZJOI又要举办了,但是老牌出题人九条可怜突然有急事要回趟英国。 “就交给你们啦!一定没有问题desu!”,说完可怜就跑远了。 忍,爱丽丝,绫和阳子目送着远去的可怜,感到有点茫然,毕竟,ZJOI只剩不到三星期了。 “既然是可怜酱留下的任务,那我们一定要努力完成了,毕竟我才是姐姐”,爱丽丝说。 于是众人就开始热火朝天地出题了,“希望这是第一次也是最后一次了”大家都不约而同地想。 同时,题目主角就定为九条可怜了! 【题目描述】 九条可怜是一个喜欢树的女孩子,她想生成两棵均有n 个节点的树。 第一棵树的生成方式是:
- 节点1 作为树的根。
- 对于i ∈[2, n],从[1, i −1] 中选取一个节点作为i 的父亲。 第二棵树的生成方式是:
- 节点n 作为树的根。
- 对于i ∈[1, n −1],从[i + 1, n] 中选取一个节点作为i 的父亲。 九条可怜希望对于任意i ∈[1, n] ,若第一棵树中的节点i 为叶子,那么第二棵树中的节点i 为 非叶子;若第一棵树中的节点i 为非叶子,那么第二棵树中的节点i 为叶子。一个节点被称为叶子当 且仅当没有节点的父亲是它。 九条可怜希望你统计生成两棵树的方案数是多少。具体地,你需要对于所有n ∈[2, N] 都计算方 案数。两种方案不同当且仅当存在一棵树中的一个节点i ,两种方案中它的父亲不同。因为答案可能 很大,你只需要输出答案对M 取模后的结果。 【输入格式】 从文件tree.in 中读入数据。 第一行输入两个整数N, M,表示树的节点上限以及模数。 【输出格式】 输出到文件tree.out 中。 输出N −1 行,每行一个整数。 具体地,第i 行输出n = i + 1 时的答案对M 取模后的值。 【样例输入】 见下发文件中的tree ex1.in和tree ex2.in。 第2 页 共7 页
ZJOI 2022 第一试 树(tree) 【样例输出】 见下发文件中的tree ex1.ans和tree ex2.ans。 【数据范围与提示】 对于所有测试点:保证10 ≤M ≤230。 每个测试点的具体限制见下表: 测试点编号 N ≤ 特殊限制 1 10 无 2 20 保证M 为质数 3 50 无 4 50 保证M 为质数 5 100 无 6 100 保证M 为质数 7 500 无 8 500 保证M 为质数 9 500 无 10 500 保证M 为质数 第3 页 共7 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5 998244353
1
2
12
120
样例 2
50 10007
1
2
12
120
1928
4340
3971
8636
815
1971
1138
4657
4784
7523
951
6104
2967
9876
5030
4921
4936
8826
5951
3506
1431
7190
8667
655
5143
4548
1416
7845
3569
4220
8273
2745
1650
7824
8477
3716
366
9885
5166
7416
6843
1214
7262
3538
681