303753: CF724F. Uniformly Branched Trees

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Uniformly Branched Trees

题意翻译

题目大意:给定三个数 $n, d, \mathit{mod}$,求有多少种 $n$ 个点的不同构的树满足:除了度数为 $1$ 的结点外,其余结点的度数均为 $d$。答案对质数 $\mathit{mod}$ 取模。 数据范围:$1 \le n \le 1000$,$2 \le d \le 10$,${10}^8 \le \mathit{mod} \le {10}^9$。

题目描述

A tree is a connected graph without cycles. Two trees, consisting of $ n $ vertices each, are called isomorphic if there exists a permutation $ p:{1,...,n}→{1,...,n} $ such that the edge $ (u,v) $ is present in the first tree if and only if the edge $ (p_{u},p_{v}) $ is present in the second tree. Vertex of the tree is called internal if its degree is greater than or equal to two. Count the number of different non-isomorphic trees, consisting of $ n $ vertices, such that the degree of each internal vertex is exactly $ d $ . Print the answer over the given prime modulo $ mod $ .

输入输出格式

输入格式


The single line of the input contains three integers $ n $ , $ d $ and $ mod $ ( $ 1<=n<=1000 $ , $ 2<=d<=10 $ , $ 10^{8}<=mod<=10^{9} $ ) — the number of vertices in the tree, the degree of internal vertices and the prime modulo.

输出格式


Print the number of trees over the modulo $ mod $ .

输入输出样例

输入样例 #1

5 2 433416647

输出样例 #1

1

输入样例 #2

10 3 409693891

输出样例 #2

2

输入样例 #3

65 4 177545087

输出样例 #3

910726

Input

题意翻译

题目大意:给定三个数 $n, d, \mathit{mod}$,求有多少种 $n$ 个点的不同构的树满足:除了度数为 $1$ 的结点外,其余结点的度数均为 $d$。答案对质数 $\mathit{mod}$ 取模。 数据范围:$1 \le n \le 1000$,$2 \le d \le 10$,${10}^8 \le \mathit{mod} \le {10}^9$。

加入题单

上一题 下一题 算法标签: