No.2917 二重木
タグ : / 解いたユーザー数 13
作問者 : 👑
p-adic
/ テスター :
hotman78
注意
この問題の実行時間制限は3000[ms]です。
問題文
入力に正整数 $N$ と素数 $P$ が与えられます。
$N$ 頂点のラベル付き木 $T$ とその誘導部分グラフ $T'$ であって木であるものの組 $(T,T')$ を、ここではサイズ $N$ の二重木と呼びます。
厳密な用語の説明はこちらです。（クリックで開く）
木とは、（自己ループと多重辺のない）無向グラフであって連結でありかつ閉路のないもののことです。ただし無向グラフの連結性には頂点集合が空でないことを課します。
$N$ 頂点のラベル付き木とは（等価な定式化は複数ありますがそのうちの１つは）、木 $T$ であって以下の $2$ 条件を全て満たすもののことです：
- $T$ の頂点集合は $N$ 以下の正整数全体の集合である。
- $T$ の辺は、その $2$ 頂点 $u,v$ を用いて $\{u,v\}$ と表される。
無向グラフ $(V,E)$ の誘導部分グラフとは、無向グラフ $(V',E')$ であって $V' \subset V$ かつ $E'$ が $E$ に属す辺であって $V'$ の $2$ 点を結ぶもの全体の集合であるもののことです。
サイズ $N$ の二重木の総数を $P$ で割った余りを求めてください。
入力
入力は以下の形式で標準入力から $1$ 行で与えられます：
- $1$ 行目に $N, P$ が半角空白区切りで与えられます。
$N$ $P$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^3$ を満たす整数である。
- $P$ は $N \leq P \leq 10^9$ を満たす素数である。
出力
サイズ $N$ の二重木の総数を $P$ で割った余りを $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 3
出力
1
サイズ $1$ の木は
- 辺を持たない木 $T_1$
に限られ、$T_1$ の誘導部分グラフであって木であるものは
- $T_1$ 自身
に限られます。従ってサイズ $1$ の二重木は
- $(T_1,T_1)$
の $1$ 個しかありません。$1$ を $P = 3$ で割った余り $1$ を出力してください。
サンプル2
入力
2 5
出力
3
サイズ $2$ の木は
- $\{1,2\}$ のみを辺に持つ木 $T_{1 \leftrightarrow 2}$
の $1$ 個に限られ、$T_{1 \leftrightarrow 2}$ の誘導部分グラフであって木であるものは
- $T_{1 \leftrightarrow 2}$ 自身
- $1$ のみを頂点に持つ誘導部分グラフ $T_1$
- $2$ のみを頂点に持つ誘導部分グラフ $T_2$
の $3$ 個あります。従ってサイズ $2$ の二重木は
- $(T_{1 \leftrightarrow 2},T_{1 \leftrightarrow 2})$
- $(T_{1 \leftrightarrow 2},T_1)$
- $(T_{1 \leftrightarrow 2},T_2)$
の $3$ 個あります。$3$ を $P = 5$ で割った余り $3$ を出力してください。
サンプル3
入力
3 7
出力
4
サイズ $3$ の木は
- $\{1,2\}, \{2,3\}$ を辺に持つ木 $T_{1 \leftrightarrow 2 \leftrightarrow 3}$
- $\{1,3\}, \{2,3\}$ を辺に持つ木 $T_{1 \leftrightarrow 3 \leftrightarrow 2}$
- $\{1,2\}, \{1,3\}$ を辺に持つ木 $T_{2 \leftrightarrow 1 \leftrightarrow 3}$
の $3$ 個あります。例えば $T_{1 \leftrightarrow 2 \leftrightarrow 3}$ の誘導部分グラフであって木であるものは
- $T_{1 \leftrightarrow 2 \leftrightarrow 3}$ 自身
- $1,2$ を頂点に持つ誘導グラフ $T_{1 \leftrightarrow 2}$
- $2,3$ を頂点に持つ誘導グラフ $T_{2 \leftrightarrow 3}$
- $1$ のみを頂点に持つ誘導部分グラフ $T_1$
- $2$ のみを頂点に持つ誘導部分グラフ $T_2$
- $3$ のみを頂点に持つ誘導部分グラフ $T_3$
の $6$ 個あります。他のサイズ $3$ の木についても同様に $6$ 個ずつ誘導部分グラフであって木であるものがあります。従ってサイズ $3$ の二重木は $3 \times 6 = 18$ 個あります。$18$ を $P = 7$ で割った余り $4$ を出力してください。
サンプル4
入力
4 11
出力
10
サイズ $4$ の二重木は $164$ 個あります。$164$ を $P = 11$ で割った余り $10$ を出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。