No.1483 Many Graph in Namori
タグ : / 解いたユーザー数 9
作問者 :
PCTprobability
/ テスター :
beet
nok0
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$
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もしくは右上の雲マークをクリックしてアカウントを作成してください。