QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+10]

# 9561. 树数叔术

Statistics

时间限制:2 秒,空间限制:512 MB。

题面描述

给定 N,V,求 T$N$ f(T)P 取模后的结果。

对于一棵 N 个点的有标号无根树 T,定义 f(T) 为合法的给每个节点赋权的方案数,令 i 号点的权值 ai,定义一个赋权方案合法,当且仅当对于所有树上的所有非空连通块 S,都满足:

mex({aiiS})=min

此处定义 \text{mex}(E)E 集合内未出现过的最小非负整数,\min(E)E 集合内元素的最小值。特别地,定义 \text{mex}(\emptyset) = 0, \min(\emptyset) = V + 1

输入格式

一行输入三个数 N, V, P

输出格式

一行输出一个数,表示 \sum_{T} 是一棵 N 个点的有标号无根树 f(T)P 取模后的结果。

测试样例

样例 1

输入

5 3 998244353

输出

2280

样例 2, 3, 4

见下发文件。

数据范围

对于全部数据,满足:

1 \leq N \leq 150, \quad 1 \leq V \leq 10^9, \quad 3 \leq P \leq 1.01 \times 10^9

子任务 分值 N\leq
1 5 4
2 15 6
3 30 50
4 50 150