No.2917 Double Tree
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:
- The vertex set of $T$ is the set of all positive integers less than or equal to $N$.
- 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
- the tree $T_1$ with no edges,
and the only induced subgraph of $T_1$ that is a tree is
- $T_1$ itself.
Therefore, there is only $1$ double tree of size $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
- 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:
- $T_{1 \leftrightarrow 2}$ itself
- the induced subgraph $T_1$ whose only vertex is $1$
- the induced subgraph $T_2$ whose only vertex is $2$
Therefore, there are $3$ double trees of size $2$:
- $(T_{1 \leftrightarrow 2},T_{1 \leftrightarrow 2})$
- $(T_{1 \leftrightarrow 2},T_1)$
- $(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$:
- the tree $T_{1 \leftrightarrow 2 \leftrightarrow 3}$ with edges $\{1,2\}, \{2,3\}$
- the tree $T_{1 \leftrightarrow 3 \leftrightarrow 2}$ with edges $\{1,3\}, \{2,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:
- $T_{1 \leftrightarrow 2 \leftrightarrow 3}$ itself
- the induced graph $T_{1 \leftrightarrow 2}$ with vertices $1,2$
- the induced graph $T_{2 \leftrightarrow 3}$ with vertices $2,3$
- the induced subgraph $T_1$ whose only vertex is $1$
- the induced subgraph $T_2$ whose only vertex is $2$
- 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もしくは右上の雲マークをクリックしてアカウントを作成してください。
hotman78