問題一覧 > 通常問題

No.2135 C5

レベル : / AI推定難易度 : 2250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 25
作問者 : shobonvip / テスター : 👑 hamamu taiga0629kyopro
お気に入りにしたユーザー ProblemId : 8725 / 自分の提出
問題文最終更新日: 2022-11-23 21:46:56
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 369 (順位表) の他の問題:

Problem Statement

Find the number, modulo $998244353$, of undirected simple graphs $G=(V, E)$ with $N$ vertices and $M$ edges, whose vertices are numbered $1, 2, \cdots, N$ and whose edges are unnumbered, that satisfy the following condition.

  • For every subset $V'$ of $V$ with $|V'| = 5$, the induced subgraph of $V$ by $V'$ contains a cycle of length $5$.
  • Note

    For an undirected graph $G=(V,E)$ and a subset $V'$ of its vertices, the induced subgraph of $V$ by $V'$ is the undirected graph $G'=(V',E')$ satisfying the following condition.

  • The edge set $E'$ consists of all edges in $E$ whose both endpoints are contained in $V'$.
  • Input

    $N$ $M$
    
  • $5 \le N \le 300$
  • $0 \le M \le \frac{N(N-1)}{2}$
  • All inputs are integers.
  • Output

    Print a newline at the end.

    Sample

    Sample 1
    Input
    5 6
    Output
    60

    The answer is $60$.

    For example, Graph 1 and Graph 2 below both satisfy the condition. In this case, the only $V'$ to consider is $\{1, 2, \cdots, 5\}$, and in both graphs the vertices $1, 2, \cdots, 5$ form a cycle of length $5$. Since the vertices are numbered, these two graphs are counted as different.

    Sample 2
    Input
    7 13
    Output
    0

    There may be no graph satisfying the condition.

    Sample 3
    Input
    8 22
    Output
    49056

    Sample 4
    Input
    300 44687
    Output
    203359716

    Print the answer modulo $998244353$.

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