Graph Smoothing

题目描述

我们有一个有 $N$ 个顶点和 $M$ 条边的简单无向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。
第 $i$ 条边连接顶点 $X_i$ 和顶点 $Y_i$。最初，顶点 $i$ 上写着一个整数 $A_i$。
你将进行如下操作 $K$ 次：

从 $M$ 条边中均匀随机且相互独立地选择一条。令 $x$ 为该边所连接的两个顶点上所写数字的算术平均值。用 $x$ 替换这两个顶点上写的数。

对于每个顶点 $i$，求在 $K$ 次操作之后该顶点上所写数字的期望值，并按 Notes 中所述对 $(10^9 + 7)$ 取模后输出。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $K$ $A_1$ $A_2$ $A_3$ $\dots$ $A_N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $X_3$ $Y_3$ $\hspace{15pt} \vdots$ $X_M$ $Y_M$

输出格式

输出 $N$ 行。
第 $i$ 行应当包含在 $K$ 次操作之后该顶点上所写数字的期望值，按 Notes 中所述对 $(10^9 + 7)$ 取模后的值。

3 2 1
3 1 5
1 2
1 3

3
500000005
500000008

3 2 2
12 48 36
1 2
1 3

750000036
36
250000031

4 5 1000
578 173 489 910
1 2
2 3
3 4
4 1
1 3

201113830
45921509
67803140
685163678

提示

$2 \le N \le 100$ $1 \le M \le \frac{N(N - 1)}{2}$ $0 \le K \le 10^9$ $0 \le A_i \le 10^9$ $1 \le X_i \le N$ $1 \le Y_i \le N$ 给定的图是简单图。 输入中的所有数值均为整数。输出有理数时，先将其表示为分数 $\frac{y}{x}$，其中 $x$ 和 $y$ 为整数且 $x$ 不被 $(10^9+7)$ 整除（在本题的约束下，总是可行）。
然后，输出在 $0$ 到 $(10^9+6)$（包含两端）之间唯一的整数 $z$，使得 $xz \equiv y \pmod {10^9+7}$。如果在唯一的一次操作中选择了边 $1$：顶点 $1,2,3$ 上的数将分别变为 $2,2,5$。 如果在唯一的一次操作中选择了边 $2$：顶点 $1,2,3$ 上的数将分别变为 $4,1,4$。

因此，顶点 $1,2,3$ 上的数字的期望值分别为 $3, \frac{3}{2}, \frac{9}{2}$。
如果按 Notes 中所述将它们对 $(10^9 + 7)$ 取模，分别为 $3, 500000005, 500000008$。
如果在第 $1$ 次操作中选择了边 $1$： 顶点 $1,2,3$ 上的数将分别为 $30, 30, 36$。
如果在第 $2$ 次操作中选择了边 $1$： 顶点 $1,2,3$ 上的数将分别为 $30, 30, 36$。 如果在第 $2$ 次操作中选择了边 $2$： 顶点 $1,2,3$ 上的数将分别为 $33, 30, 33$。

如果在第 $1$ 次操作中选择了边 $2$： 顶点 $1,2,3$ 上的数将分别为 $24, 48, 24$。
如果在第 $2$ 次操作中选择了边 $1$： 顶点 $1,2,3$ 上的数将分别为 $36, 36, 24$。 如果在第 $2$ 次操作中选择了边 $2$： 顶点 $1,2,3$ 上的数将分别为 $24, 48, 24$。

以上四种情形各以概率 $\frac{1}{4}$ 发生，所以顶点 $1,2,3$ 上的数字的期望值分别为 $\frac{123}{4}, \frac{144}{4} (=36), \frac{117}{4}$。

标签: AtCoder|abc199F

来源

AtCoder|abc199F