Uniformly Branched Trees
Contest: Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)
Difficulty rating: 2700
Tags: combinatorics, dp, trees

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 (pu, pv) 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.

Input format:
The single line of the input contains three integers n, d and mod (1 ≤ n ≤ 1000, 2 ≤ d ≤ 10, 108 ≤ mod ≤ 109)  — the number of vertices in the tree, the degree of internal vertices and the prime modulo.

Output format:
Print the number of trees over the modulo mod.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
5 2 433416647

Example output:
1

Example input:
10 3 409693891

Example output:
2

Editorial:
At first, we will calculate the following dynamic programming: trees(i, j, k) will be the number of rooted trees, where the root has exactly j directed subtrees, the maximum size of which does not exceed k, and the degree of internal vertices is equal to d (except for the root).
Calculation of the value of the dynamics for fixed parameters is divided into two cases:
1. there are on subtrees of size k at all. In this case, you can take the value of trees(i,  j,  k - 1);
2. there are t > 0 subtrees of size k. In this case, we got $$\text{trees}(i-t*k, j-t, k-1) * \binom{\text{trees}(k, d-1, k-1)+t-1}{t}$$ different trees.
The main idea here is that we do not distinguish trees that differ only by a permutation of the sons for some vertices (this is where the number of combinations come from). It's enough to set some order in which we will place the sons of all vertices. In this case, they are arranged in the order of ascending sizes and the index number of its subtrees (all the trees of fixed size can be written in one big list and enumerated).
Now we need to count the number of unrooted trees. Let's get rid of this restriction, by rooting all the trees using some vertex. For this vertex, we will take the centroid (the vertex, after removing which, the tree splits into connected components, with the sizes not larger than the half of the original size of the tree). The advantage of this choice is that any tree always have either one or two centroids.
The number of trees that have exactly one centroid is equal to $$trees(n,d,\left[\frac{n}{2}\right])$$. The fact that we chose the centroid, implies that the size of subtrees cannot exceed $$\left\lfloor \frac{n}{2} \right\rfloor$$.
The number of trees that have exactly two centroids is equal to $$( \operatorname { t r e e s } ( { \frac { n } { 2 } }, d - 1, { \frac { n } { 2 } } - 1 ) + 1 ) _ { 2 }$$ if n is divisible by 2, and zero otherwise. If there are two centroids, they will be connected by an edge, and the removing of this edge will split the graph into two parts, each of which will contain exactly $$\frac{\pi}{2}$$ vertices.
The resulting complexity of this solution is O(n2 * d2).