問題一覧 > 通常問題

No.1483 Many Graph in Namori

レベル : / AI推定難易度 : 2800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 9
作問者 : PCTprobability / テスター : beet fairy_lettuce nok0 ygussany
お気に入りにしたユーザー ProblemId : 6025 / 自分の提出
問題文最終更新日: 2021-04-17 00:54:30
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 291 (順位表) の他の問題:

Problem Statement

You are given a simple connected undirected graph $G$ with $N$ vertices and $N$ edges, and a positive integer $K$. The $i$-th edge connects vertex $a_i$ and vertex $b_i$.

Let $C$ be the set of connected subgraphs of $G$. Note that even isomorphic graphs are distinguished if their vertex numbers differ.

For $S \in C$, define $x(S),y(S)$ as the number of vertices in $S$ with degree at most $1$ and the number of vertices in $S$ with degree at least $2$, respectively.

Find the value of $\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$.

Input

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

  • All inputs are integers.
  • $3 \le N \le 10^5$
  • $2 \le K \le 6$
  • $1 \le a_i,b_i \le N$
  • $a_i \neq b_i$
  • If $i \neq j$, then $(a_i,b_i) \neq (a_j,b_j)$.
  • If $i \neq j$, then $(a_i,b_i) \neq (b_j,a_j)$.
  • The given graph is connected.
  • Output

    Output the answer in $1$ line.

    Print a newline at the end.

    Sample

    Sample 1
    Input
    4 2
    1 2
    2 3
    3 1
    3 4
    Output
    33

    Let $f(S)=K^{x(S)}(1 - K)^{N - x(S) - y(S)} \times \left(x(S) + y(S)\right)$.

    For the subgraph consisting of edges $1,3$, we have $x(S)=2,y(S)=1,f(S)=2^2 \times (1-2)^{4-2-1} \times (2+1)=-12$.

    For the subgraph consisting of edges $1,2,3$, we have $x(S)=0,y(S)=3,f(S)=2^0 \times (1-2)^{4-0-3} \times (0+3)=-3$.

    For the subgraph consisting only of vertex $1$, we have $x(S)=1,y(S)=0,f(S)=2^1 \times (1-2)^{4-1-0} \times (1+0)=-2$.

    Note that a subgraph is not necessarily a tree, and it may also consist of $1$ vertex.

    Sample 2
    Input
    4 6
    1 2
    2 3
    3 1
    3 4
    Output
    2661

    Sample 3
    Input
    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
    Output
    973949412

    Find the remainder when divided by $998244353$.

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