V. [CmdOI2019] 黑白图

Type: RemoteJudge

1000ms

125MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

你看见了一张奇怪的图。

有一张 $n$ 个点， $m$ 条边的简单无向连通图，点可以染上黑色或者白色。

这个图比较稀疏，具体来讲有两种情况。

我们定义一张黑白图的权值为：其黑色连通块大小的 $k$ 次方和。

现在图的形态已经确定，但是每个点上的颜色尚未确定，对于第 $i$ 个点。其有百分之 $p_i$ 的可能是黑色，反之则是白色。

求图的期望权值对 $998244353$ 取模的结果。

第一行包括三个正整数 $n,m,k$ ，意义如题面所述。

接下来一行 $n$ 个数依次表示 $p_{1\sim n}$ 。

后 $m$ 行，每行两个数 $f,t$ ，表示图的一条无向边 $f\leftrightarrow t$ 。

输出一个整数，表示图的期望权值对 $998244353$ 取模的结果。

5 4 3
50 50 50 50 50
1 2
2 3
2 4
2 5

6 5 2
20 30 40 50 60 70
1 2
2 3
2 4
2 5
4 6

397301258

10 10 2
39 76 71 86 36 38 36 44 63 37 
4 5
2 10
6 10
1 8
5 10
8 10
7 10
3 10
10 9
5 3

361859252

数据点编号	$n$	$m$	$k$	性质1	性质2	分数
1	$16$	$n-1$	$5$	$\sqrt{}$	-	$5$
2	$50$		$3$		$\sqrt{}$
3	$50$		$5$		-
4	$500$		$1$	-	-
5	$2\times 10^5$		$3$	$\sqrt{}$	$\sqrt{}$
6			$2$	-	$\sqrt{}$
7			$4$		-	$10$
8	$16$	$n$	$3$
9	$500$		$3$
10	$50000$		$2$
11	$2\times 10^5$		$4$	$\sqrt{}$
12			$5$	-
13			$5$	-

特殊性质 $1$ ： $p_i=50$ 。

特殊性质 $2$ ：图退化成一条链，其中 $i$ 向 $i+1$ 连边。