#1861. 树数叔术

    ID: 1861 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1823来源:qoj.ac数据:公开样例动态规划数学

树数叔术

树数叔术

题目描述

标题: 树数叔术 - Problem - QOJ.ac

#9561. 树数叔术

Statistics

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