問題一覧 > 通常問題

No.2733 Just K-times TSP

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

問題文

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

  • すべての i (i=1,…,N)i \ (i=1, \ldots, N) に対して、頂点 ii はちょうど KK 回用いられる
ウォークとは グラフ GG 上のウォークとは、kk 個（ kk は正整数）の頂点と k−1k-1 個の辺を交互に並べた列 (v1,e1,v2,…,vk−1,ek−1,vk)(v_1, e_1, v_2, \ldots, v_{k-1}, e_{k-1}, v_k) であって、辺 eie_i が頂点 viv_i と vi+1v_{i+1} を結ぶ辺であるようなものを指す。

制約

  • 1≤N≤61 \le N \le 6
  • 0≤M≤N(N−1)20 \le M \le \frac{N (N - 1)}{2}
  • 1≤K≤81 \le K \le 8
  • 1≤ui<vi≤N(1≤i≤M)1 \le u_i < v_i \le N (1 \le i \le M)
  • (ui,vi)≠(uj,vj)(1≤i<j≤M) (u_i, v_i) \ne (u_j, v_j) (1 \le i < j \le M)
  • 入力は全て整数

入力

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

N M KN \ M \ K
u1 v1u_1 \ v_1
⋮\vdots 
uM vMu_M \ v_M

出力

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

サンプル

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

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

  • 1→2→1→2→3→4→3→41→2→1→2→3→4→3→4
  • 2→1→2→1→3→4→3→42→1→2→1→3→4→3→4
  • 4→3→1→2→1→2→3→44→3→1→2→1→2→3→4
  • 4→3→2→1→2→1→3→44→3→2→1→2→1→3→4
  • 4→3→4→3→1→2→1→24→3→4→3→1→2→1→2
  • 4→3→4→3→2→1→2→14→3→4→3→2→1→2→1

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

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