F. Uniformly Branched Trees

Codeforces

IDCF724F

Time1000ms

Memory256MB

Difficulty—

combinatoricsdptrees

English · Original

Chinese · Translation

Formal · Original

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_. ## Input 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 Print the number of trees over the modulo _mod_. [samples]

树是一个无环的连通图。两棵各有 #cf_span[n] 个顶点的树称为 _同构_ 的，当且仅当存在一个排列 #cf_span[p: {1, ..., n} → {1, ..., n}]，使得边 #cf_span[(u, v)] 出现在第一棵树中，当且仅当边 #cf_span[(pu, pv)] 出现在第二棵树中。若一个顶点的度数大于或等于二，则称其为内部顶点。计算具有 #cf_span[n] 个顶点的不同非同构树的数量，要求每个内部顶点的度数 *恰好* 为 #cf_span[d]。请对给定的素数模数 #cf_span[mod] 取模后输出答案。输入的一行包含三个整数 #cf_span[n], #cf_span[d] 和 #cf_span[mod]（#cf_span[1 ≤ n ≤ 1000], #cf_span[2 ≤ d ≤ 10], #cf_span[108 ≤ mod ≤ 109]），分别表示树的顶点数、内部顶点的度数和素数模数。请输出满足条件的树的数量对 #cf_span[mod] 取模的结果。 ## Input 输入的一行包含三个整数 #cf_span[n], #cf_span[d] 和 #cf_span[mod]（#cf_span[1 ≤ n ≤ 1000], #cf_span[2 ≤ d ≤ 10], #cf_span[108 ≤ mod ≤ 109]），分别表示树的顶点数、内部顶点的度数和素数模数。 ## Output 请输出满足条件的树的数量对 #cf_span[mod] 取模的结果。 [samples]

**Definitions** Let $ n, d, \text{mod} \in \mathbb{Z} $ with $ 1 \leq n \leq 1000 $, $ 2 \leq d \leq 10 $, and $ 10^8 \leq \text{mod} \leq 10^9 $, where mod is prime. Let $ T $ be a tree on $ n $ vertices such that every internal vertex (degree $ \geq 2 $) has degree exactly $ d $. Leaf vertices (degree 1) are allowed. **Constraints** 1. $ T $ is connected and acyclic. 2. Every vertex in $ T $ has degree either 1 or $ d $. 3. Let $ \ell $ be the number of leaves, $ i $ the number of internal vertices. Then: $$ \ell + i = n $$ $$ \ell \cdot 1 + i \cdot d = 2(n - 1) $$ (Handshaking lemma: sum of degrees = $ 2|E| = 2(n-1) $) **Objective** Count the number of non-isomorphic trees satisfying the above constraints, modulo `mod`.

Samples

Input #1

5 2 433416647

Output #1

Input #2

10 3 409693891

Output #2

Input #3

65 4 177545087

Output #3

API Response (JSON)

{
  "problem": {
    "name": "F. Uniformly Branched Trees",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF724F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A tree is a connected graph without cycles.\n\nTwo trees, consisting of _n_ vertices each, are called _isomorphic_ if there exists a permutation _p_: {1, ..., _n_} → {1, ..., _n_} such that the edge (_u...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "树是一个无环的连通图。\n\n两棵各有 #cf_span[n] 个顶点的树称为 _同构_ 的，当且仅当存在一个排列 #cf_span[p: {1, ..., n} → {1, ..., n}]，使得边 #cf_span[(u, v)] 出现在第一棵树中，当且仅当边 #cf_span[(pu, pv)] 出现在第二棵树中。\n\n若一个顶点的度数大于或等于二，则称其为内部顶点。\n\n计算具有 #cf_span...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, d, \\text{mod} \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 1000 $, $ 2 \\leq d \\leq 10 $, and $ 10^8 \\leq \\text{mod} \\leq 10^9 $, where mod is prime.  \nLet $ T $ be a tree on $ n $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments