UOJ Logo Universal Online Judge

UOJ

#740. 【ZJOI2022】树

附件下载 统计

题目背景

一年一度的ZJOI又要举办了,但是老牌出题人九条可怜突然有急事要回趟英国。

“就交给你们啦!一定没有问题desu!”,说完可怜就跑远了。

忍,爱丽丝,绫和阳子目送着远去的可怜,感到有点茫然,毕竟,ZJOI只剩不到三星期了。

“既然是可怜酱留下的任务,那我们一定要努力完成了,毕竟我才是姐姐”,爱丽丝说。

于是众人就开始热火朝天地出题了,“希望这是第一次也是最后一次了”大家都不约而同地想。

同时,题目主角就定为九条可怜了!

题目描述

九条可怜是一个喜欢树的女孩子,她想生成两棵均有 $n$ 个节点的树。

第一棵树的生成方式是:

  1. 节点 $1$ 作为树的根。
  2. 对于 $i \in [2,n]$,从 $[1, i − 1]$ 中选取一个节点作为 $i$ 的父亲。

第二棵树的生成方式是:

  1. 节点 $n$ 作为树的根。
  2. 对于 $i\in [1,n-1]$,从 $[i + 1, n]$ 中选取一个节点作为 $i$ 的父亲。

九条可怜希望对于任意 $i\in [1,n]$ ,若第一棵树中的节点 $i$ 为叶子,那么第二棵树中的节点 $i$ 为 非叶子;若第一棵树中的节点 $i$ 为非叶子,那么第二棵树中的节点 $i$ 为叶子。一个节点被称为叶子当 且仅当没有节点的父亲是它。

九条可怜希望你统计生成两棵树的方案数是多少。具体地,你需要对于所有 $n\in [2,N]$ 都计算方案数。两种方案不同当且仅当存在一棵树中的一个节点 $i$ ,两种方案中它的父亲不同。因为答案可能很大,你只需要输出答案对 $M$ 取模后的结果。

输入格式

第一行输入两个整数 $N, M$,表示树的节点上限以及模数。

输出格式

输出 $N − 1$ 行,每行一个整数。

具体地,第 $i$ 行输出 $n = i + 1$ 时的答案对 $M$ 取模后的值。

样例一

input

5 998244353

output

1
2
12
120

样例二

见附件下载。

限制与约定

对于所有测试点:保证 $10\leq M\leq 2^{30}$。

每个测试点的具体限制见下表:

测试点编号 $n\leq$ 特殊限制
$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$ 为质数

时间限制:$2\texttt{s}$

空间限制:$1024\texttt{MB}$