問題一覧 > 通常問題

No.1667 Forest

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 82
作問者 : だれ / テスター : nok0
お気に入りにしたユーザー ProblemId : 6687 / 自分の提出
問題文最終更新日: 2026-04-28 14:42:35
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 312 (順位表) の他の問題:

Problem Statement

You are given integers $N,\ MOD$. Solve the following problem for each of $M=0,1,\cdots,N-1$.

  • Find the number, modulo $MOD$, of simple undirected graphs with $N$ vertices and $M$ edges that have no cycles, where vertices are distinguished and edges are not distinguished.

    • Input

    $N$ $MOD$

    • All input values are integers.
    • $1\leq N\leq 300$
    • $10^8\leq MOD\leq 10^9+9$
    • $MOD$ is prime.

    Output

    Print $N$ lines. On the $i$-th line $(1\leq i\leq N)$, print the answer for $M=i-1$.

    Sample

    Sample 1
    Input
    3 1000000007
    Output
    1
3
3

    For $M=0$, the only possible graph is the empty graph, so there is $1$ way.

    For $M=1$, considering which $2$ vertices to connect with the edge, there are ${}_{3}{\rm C}_{2}=3$ ways.

    For $M=2$, the graph is a path graph of length $2$, and there are $3$ such graphs.

    Sample 2
    Input
    4 1000000009
    Output
    1
6
15
16

    Sample 3
    Input
    12 998244353
    Output
    1
66
2145
45540
705375
8411634
79170399
590412240
433549821
805199858
641925078
26214338

    Print the remainder when divided by $MOD$.

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