No.1483 Many Graph in Namori

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1483 Many Graph in Namori

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 8
作問者 :

PCTprobability / テスター :

beet

fairy_lettuce

nok0 👑

ygussany

2 ProblemId : 6025 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-04-17 00:54:30

問題文

$N$ 頂点 $N$ 辺の単純連結無向グラフ $G$ と正整数 $K$ が与えられます。 $i$ 本目の辺は頂点 $a_{i}$ と頂点 $b_{i}$ を繋いでいます。

$G$ の部分グラフのうち連結であるものからなる集合を $C$ とします。ただし、同型なグラフであっても頂点の番号が違う場合区別することに注意してください。

$S \in C$ に対して、 $x (S), y (S)$ をそれぞれ、 $S$ に含まれる次数 $1$ 以下の頂点の個数、 $S$ に含まれる次数 $2$ 以上の頂点の個数と定義します。

$(\sum_{S \in C} K^{x (S)} \times (1 - K)^{N - x (S) - y (S)} \times (x (S) + y (S))) mod 998244353$ の値を求めてください。

入力

 $N K$ 
 $a_{1} b_{1}$ 
 $a_{2} b_{2}$ 
 $⋮$ 
 $a_{N} b_{N}$

入力は全て整数である。

3 \leq N \leq 10^{5}

2 \leq K \leq 6

1 \leq a_{i}, b_{i} \leq N

a_{i} \neq b_{i}

i \neq j

ならば

(a_{i}, b_{i}) \neq (a_{j}, b_{j})

i \neq j

ならば

(a_{i}, b_{i}) \neq (b_{j}, a_{j})

与えられるグラフは連結である。

出力

答えを $1$ 行に出力してください。

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

サンプル

サンプル1

入力

出力

$f (S) = K^{x (S)} (1 - K)^{N - x (S) - y (S)} \times (x (S) + y (S))$ とします。

辺 $1, 3$ からなる部分グラフについて $x (S) = 2, y (S) = 1, f (S) = 2^{2} \times (1 - 2)^{4 - 2 - 1} \times (2 + 1) = - 12$ です。

辺 $1, 2, 3$ からなる部分グラフについて $x (S) = 0, y (S) = 3, f (S) = 2^{0} \times (1 - 2)^{4 - 0 - 3} \times (0 + 3) = - 3$ です。

頂点 $1$ だけからなる部分グラフについて $x (S) = 1, y (S) = 0, f (S) = 2^{1} \times (1 - 2)^{4 - 1 - 0} \times (1 + 0) = - 2$ です。

部分グラフは木であるとは限らない、また頂点 $1$ 個からなる場合もあることに注意してください。

サンプル2

入力

出力

サンプル3

入力

出力

973949412

$998244353$ で割った余りを求めてください。

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

yukicoder

No.1483 Many Graph in Namori

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力