問題一覧 > 通常問題

No.1667 Forest

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 79
作問者 : だれだれ / テスター : nok0nok0
8 ProblemId : 6687 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-03 22:18:26

問題文

整数 $N,\ MOD$ が与えられます。$M=0,1,\cdots,N-1$ について、次の問題を解いてください。

  • 頂点が区別され辺は区別されない $N$ 頂点 $M$ 辺の単純無向グラフであって、閉路を持たないものの個数を $MOD$ で割ったあまりを求めよ。

    • 入力

    $N$ $MOD$

  • 入力はすべて整数
  • $1\leq N\leq 300$
  • $10^8\leq MOD\leq 10^9+9$
  • $MOD$ は素数

    • 出力

    $N$ 行出力してください。$i$ 行目 $(1\leq i\leq N)$ には、$M=i-1$ のときの答えを出力してください。

    サンプル

    サンプル1
    入力
    3 1000000007
    出力
    1
3
3

    $M=0$ のとき、考えられるグラフは空グラフのみの $1$ 通りです。

    $M=1$ のとき、どの $2$ 頂点を辺で結ぶかを考えると ${}_{3}{\rm C}_{2}=3$ 通りです。

    $M=2$ のとき、グラフは長さ $2$ のパスグラフとなり、これは $3$ 通りあります。

    サンプル2
    入力
    4 1000000009
    出力
    1
6
15
16

    サンプル3
    入力
    12 998244353
    出力
    1
66
2145
45540
705375
8411634
79170399
590412240
433549821
805199858
641925078
26214338

    $MOD$ で割った余りを出力してください。

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