#1861. 树数叔术
树数叔术
树数叔术
题目描述
标题: 树数叔术 - Problem - QOJ.ac
#9561. 树数叔术
The problem was used in the following contests:
给定 N,V,求 ∑T 是一棵 N 个点的有标号无根树f(T) 对 P 取模后的结果。
对于一棵 N 个点的有标号无根树 T,定义 f(T) 为合法的给每个节点赋权的方案数,令 i 号点的权值 ai,定义一个赋权方案合法,当且仅当对于所有树上的所有非空连通块 S,都满足:
mex({ai∣i∈S})=min({ai∣i∉S})
此处定义 mex(E) 为 E 集合内未出现过的最小非负整数,min(E) 为 E 集合内元素的最小值。特别地,定义 mex(∅)=0,min(∅)=V+1。
输入格式
一行输入三个数 N,V,P。
输出格式
一行输出一个数,表示 ∑T 是一棵 N 个点的有标号无根树f(T) 对 P 取模后的结果。
测试样例
样例 1
输入
5 3 998244353
输出
2280
样例 2, 3, 4
见下发文件。
数据范围
对于全部数据,满足:
1≤N≤150,1≤V≤109,3≤P≤1.01×109
子任务 分值 N≤ 1 5 4 2 15 6 3 30 50 4 50 150
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5 3 998244353
2280