問題一覧 > 教育的問題

No.2917 Double Tree

レベル : / AI推定難易度 : 2050 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 13
作問者 : 👑 p-adic / テスター : hotman78
お気に入りにしたユーザー ProblemId : 10231 / 自分の提出
問題文最終更新日: 2023-10-22 13:38:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 449 (順位表) の他の問題:

Note

The execution time limit for this problem is 3000[ms].

Problem Statement

You are given a positive integer $N$ and a prime $P$ as input.

 

Here, a pair $(T,T')$ of a labeled tree $T$ with $N$ vertices and an induced subgraph $T'$ of it that is a tree is called a double tree of size $N$.

Click here for the rigorous definitions of the terms. (Click to open)

 

A tree is an undirected graph (without self-loops or multiple edges) that is connected and has no cycles. Here, connectivity of an undirected graph requires that the vertex set be non-empty.

A labeled tree with $N$ vertices is (there are several equivalent formulations, and this is one of them) a tree $T$ satisfying both of the following $2$ conditions:

  1. The vertex set of $T$ is the set of all positive integers less than or equal to $N$.
  2. Each edge of $T$ is represented as $\{u,v\}$ using its $2$ vertices $u,v$.

An induced subgraph of an undirected graph $(V,E)$ is an undirected graph $(V',E')$ such that $V' \subset V$ and $E'$ is the set of all edges belonging to $E$ that connect $2$ points of $V'$.

 

Find the total number of double trees of size $N$, modulo $P$.

Input

The input is given from standard input in $1$ line in the following format:

  • The $1$st line contains $N, P$ separated by a single space.
$N$ $P$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 10^3$.
  • $P$ is a prime satisfying $N \leq P \leq 10^9$.

Output

Output the total number of double trees of size $N$, modulo $P$, in $1$ line.

Print a newline at the end.

Sample

Sample 1
Input
1 3
Output
1

The only tree of size $1$ is

  1. the tree $T_1$ with no edges,

and the only induced subgraph of $T_1$ that is a tree is

  1. $T_1$ itself.

Therefore, there is only $1$ double tree of size $1$:

  1. $(T_1,T_1)$

Output $1$, the remainder when $1$ is divided by $P = 3$.

Sample 2
Input
2 5
Output
3

The only tree of size $2$ is the $1$ tree

  1. the tree $T_{1 \leftrightarrow 2}$ whose only edge is $\{1,2\}$,

and there are $3$ induced subgraphs of $T_{1 \leftrightarrow 2}$ that are trees:

  1. $T_{1 \leftrightarrow 2}$ itself
  2. the induced subgraph $T_1$ whose only vertex is $1$
  3. the induced subgraph $T_2$ whose only vertex is $2$

Therefore, there are $3$ double trees of size $2$:

  1. $(T_{1 \leftrightarrow 2},T_{1 \leftrightarrow 2})$
  2. $(T_{1 \leftrightarrow 2},T_1)$
  3. $(T_{1 \leftrightarrow 2},T_2)$

Output $3$, the remainder when $3$ is divided by $P = 5$.

Sample 3
Input
3 7
Output
4

There are $3$ trees of size $3$:

  1. the tree $T_{1 \leftrightarrow 2 \leftrightarrow 3}$ with edges $\{1,2\}, \{2,3\}$
  2. the tree $T_{1 \leftrightarrow 3 \leftrightarrow 2}$ with edges $\{1,3\}, \{2,3\}$
  3. the tree $T_{2 \leftrightarrow 1 \leftrightarrow 3}$ with edges $\{1,2\}, \{1,3\}$

For example, there are $6$ induced subgraphs of $T_{1 \leftrightarrow 2 \leftrightarrow 3}$ that are trees:

  1. $T_{1 \leftrightarrow 2 \leftrightarrow 3}$ itself
  2. the induced graph $T_{1 \leftrightarrow 2}$ with vertices $1,2$
  3. the induced graph $T_{2 \leftrightarrow 3}$ with vertices $2,3$
  4. the induced subgraph $T_1$ whose only vertex is $1$
  5. the induced subgraph $T_2$ whose only vertex is $2$
  6. the induced subgraph $T_3$ whose only vertex is $3$

Similarly, each of the other trees of size $3$ also has $6$ induced subgraphs that are trees. Therefore, there are $3 \times 6 = 18$ double trees of size $3$. Output $4$, the remainder when $18$ is divided by $P = 7$.

Sample 4
Input
4 11
Output
10

There are $164$ double trees of size $4$. Output $10$, the remainder when $164$ is divided by $P = 11$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。