#P18512. DFS Order 4
DFS Order 4
DFS Order 4
Little Cyan Fish(也叫 Qingyu Xiao)喜欢 DFS 序。给定一棵有 n 个顶点的有根树 T,顶点编号为 1 到 n,根为顶点1。对每个 i(2≤i≤n),其父亲为 f_i,满足 1≤f_i<i。
DFS 序 D=(D_1,D_2,…,D_n) 是对这棵树进行深度优先搜索时,第一次访问各顶点的顺序。第 j 项的顶点在另外 j−1 个顶点之后被访问。每当一个顶点有多个儿子,必须按儿子编号递增的顺序依次访问。因此每棵有根树在本题中只有一个 DFS 序。

上图的 DFS 序为 [1,2,3,7,4,5,6]。下面的伪代码给出了原题的生成过程,树由数组 f={f_2,…,f_n} 唯一确定。
过程 dfs(x):
把 x 加入 dfs_order 的末尾
按编号递增顺序,枚举 x 的每一个儿子 y:
dfs(y)
过程 generate():
创建全局空列表 dfs_order
dfs(1)
返回 dfs_order
设 D 是 generate() 的返回值。共有 (n−1)! 种不同的父数组 f,每种表示一棵不同的树。考虑所有这些父数组,一共能得到多少个不同的 DFS 序?当且仅当某个位置 i 上 D_i 与 D'_i 不同,才认为两个 DFS 序不同。不同的树可能得到同一个 DFS 序,只计一次。
给定一个质数 P,请输出这个数量对 P 取模的结果。
输入格式
只有一行,包含两个整数 n,P,其中
- 1≤n≤800;
- 10^8≤P≤1.01×10^9;
- 保证 P 是质数。
输入只有一个测试用例,没有 T。P 不一定等于 998244353,也不保证适合某个长度的 NTT。
输出格式
输出一行,一个整数,表示不同 DFS 序数量对 P 取模的结果。
原样例1
输入:
4 114514199
输出:
2
原样例2
输入:
10 998244353
输出:
11033
原样例3
输入:
100 1000000007
输出:
270904395
原说明
第一个样例只有两个不同的 DFS 序:D_1=[1,2,3,4] 和 D_2=[1,2,4,3]。它们分别可以由父数组 f_2=1,f_3=1,f_4=1 和 f_2=1,f_3=1,f_4=2 的两棵树得到。
