#PQJ921x4007. QOJ 921_4007
QOJ 921_4007
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 页