問題一覧 > 通常問題

No.2135 C5

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : shobonvipshobonvip / テスター : hamamuhamamu taiga0629kyoprotaiga0629kyopro
15 ProblemId : 8725 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-23 21:46:56

問題文

頂点に $1, 2, \cdots, N$ の番号が付き、辺に番号が付けられていない $N$ 頂点 $M$ 辺の無向単純グラフ $G=(V, E)$ であって、次の条件を満たすものの個数を $998244353$ で割った余りで求めてください。

  • $|V'| = 5$ である $V$ の部分集合 $V'$ すべてについて、$V'$ による $V$ の誘導部分グラフは長さ $5$ の閉路を含む
    • 注記

    無向グラフ $G=(V,E)$ とその頂点の部分集合 $V'$ について、$V'$ による $V$ の誘導部分グラフとは、次の条件を満たす無向グラフ $G'=(V',E')$ のことを言います。

  • 辺集合 $E'$ は、$E$ の辺であってその両端点が $V'$ に含まれるものすべてである

    • 入力

    $N$ $M$
  • $5 \le N \le 300$
  • $0 \le M \le \frac{N(N-1)}{2}$
  • 入力は全て整数である

    • 出力

    最後に改行してください。

    サンプル

    サンプル1
    入力
    5 6
    出力
    60

    答えは $60$ 個です。

    たとえば、以下のグラフ1、グラフ2はともに条件を満たします。この場合、考えるべき $V'$ は $\{1, 2, \cdots, 5\}$ のみになり、両者とも頂点 $1, 2, \cdots, 5$ は長さ $5$ の閉路を成します。ここで、頂点は番号付けられているので、この2つのグラフは異なるものとして数えます。

    サンプル2
    入力
    7 13
    出力
    0

    条件を満たすグラフが存在しないこともあります。

    サンプル3
    入力
    8 22
    出力
    49056

    サンプル4
    入力
    300 44687
    出力
    203359716

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

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