一般难度的推式子题 - Problem

E: 可以出生成树计数相关吗[吃瓜.jpg]

X: 别

E: 啊，主要是今天弄出来一个求一种特别的矩阵的行列式的东西

X: 来个一般难度的推式子题即可

对于所有 $n$ 个节点的有根树，对每棵树的高度求和。答案对 $p$ 取模。

高度是说能从根节点走出的最长简单路径长度。

两个有根树相等，当且仅当根节点的孩子数相等，且孩子从左往右，各子树对应相等。

输入两个整数 $n, p$。

输出所有 $n$ 个节点的有根树的高度之和模 $p$。

4 998244353

注意对于样例 1：

有 $1$ 种高度为 $1$ 的树：直接有 $3$ 个孩子
有 $3$ 种高度为 $2$ 的树：
- 一个孩子，孩子下面连两个孩子
- 两个孩子，其中一个孩子是叶子，这个算两种方案，因为孩子有先后顺序，我们分为第一个孩子是叶子或者第二个孩子是叶子
有 $1$ 种高度为 $3$ 的树：一条链

10 998244353

514 998244353

867876856

对于前 $20\%$ 的数据，$n\le 50$。

对于前 $40\%$ 的数据，$n\le 400$。

对于前 $60\%$ 的数据，$n\le 1000, p = 998244353$。

对于前 $80\%$ 的数据，$n\le 2000$。

对于 $100\%$ 的数据，$1\le n\le 10^5, 9\times 10^8 \le p\le 1.01 \times 10^9$，$p$ 是质数。

QOJ.ac