問題一覧 > 通常問題

No.1483 Many Graph in Namori

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 7
作問者 : PCTprobabilityPCTprobability / テスター : beetbeet fairy_lettucefairy_lettuce nok0nok0 👑 ygussanyygussany
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$ 以上の頂点の個数と定義します。

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

入力

$N\ K$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_N\ b_N$

  • 入力は全て整数である。
  • $3 \le N \le 10^5$
  • $2 \le K \le 6$
  • $1 \le a_i,b_i \le 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
    入力
    4 2
1 2
2 3
3 1
3 4
    出力
    33

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

    辺 $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
    入力
    4 6
1 2
2 3
3 1
3 4
    出力
    2661

    サンプル3
    入力
    13 4
1 2
3 5
3 2
11 10
9 1
4 1
1 3
12 4
6 5
8 2
5 7
4 13
10 1
    出力
    973949412

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

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