問題一覧 > 通常問題

No.2135 C5

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

問題文

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

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

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

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

    • 入力

    NN MM
  • 5≤N≤3005 \le N \le 300
  • 0≤M≤N(N−1)20 \le M \le \frac{N(N-1)}{2}
  • 入力は全て整数である

    • 出力

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

    サンプル

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

    答えは 6060 個です。

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

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

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

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

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

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

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