問題一覧 > 通常問題

No.2733 Just K-times TSP

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 84
作問者 : hiro1729hiro1729 / テスター : 👑 AngrySadEightAngrySadEight kusirakusirakusirakusira FplusFplusFFplusFplusF 🦠みどりむし🦠みどりむし
1 ProblemId : 10643 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-21 18:49:28

問題文

$N$ 頂点 $M$ 辺の単純無向グラフと正整数 $K$ が与えられます。頂点には $1$ から $N$ までの番号、辺には $1$ から $M$ までの番号がつけられていて、辺 $i (1 \le i \le M)$ は頂点 $u_i$ と $v_i$ を結ぶ辺です。
このグラフ上のウォークで、以下の条件を満たすものの個数を求め、$998244353$ で割った余りを出力してください。

  • すべての $i \ (i=1, \ldots, N)$ に対して、頂点 $i$ はちょうど $K$ 回用いられる
ウォークとは グラフ $G$ 上のウォークとは、$k$ 個（ $k$ は正整数）の頂点と $k-1$ 個の辺を交互に並べた列 $(v_1, e_1, v_2, \ldots, v_{k-1}, e_{k-1}, v_k)$ であって、辺 $e_i$ が頂点 $v_i$ と $v_{i+1}$ を結ぶ辺であるようなものを指す。

制約

  • $1 \le N \le 6$
  • $0 \le M \le \frac{N (N - 1)}{2}$
  • $1 \le K \le 8$
  • $1 \le u_i < v_i \le N (1 \le i \le M)$
  • $ (u_i, v_i) \ne (u_j, v_j) (1 \le i < j \le M)$
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。 

$N \ M \ K$
$u_1 \ v_1$
$\vdots $
$u_M \ v_M$

出力

条件を満たすウォークの個数を $998244353$ で割った余りを求め、最後に改行してください。

サンプル

サンプル1
入力
4 4 2
1 2
1 3
3 4
2 3
出力
6

辺 $i$ から辺 $j$ への移動を $i→j$ と表記すると、次の $6$ 通りがあります。

  • $1→2→1→2→3→4→3→4$
  • $2→1→2→1→3→4→3→4$
  • $4→3→1→2→1→2→3→4$
  • $4→3→2→1→2→1→3→4$
  • $4→3→4→3→1→2→1→2$
  • $4→3→4→3→2→1→2→1$

サンプル2
入力
3 3 4
1 2
2 3
1 3
出力
1092

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