分数: 600 点
问题陈述
我们有一个简单的无向图 N 顶点和 M 边缘。顶点已编号 1 通过 N 且边缘已编号 1 通过 M.
边缘 i 连接顶点 X_i 和顶点 Y_i。最初,顶点 i 有一个整数
上面写着 A_i 。
您将执行以下操作 K 次:
- 从以下选项中选择一项 M 边缘均匀随机且独立于其他选择。让 x 是写在该边连接的两个顶点上的数字的算术平均值。将这些顶点上写的每个数字替换为 x.
对于每个顶点 i,找到之后写在该顶点上的数字的期望值 K 运算,并打印模数 (10^9 + 7) 如注释中所述。
注释
打印有理数时,首先将其表示为分数 \frac{y}{x},其中 x 和 y 是整数并且 x 不能被整除 (10^9+7) (在这个问题的约束下,这样的表示总是可能的)。
然后,打印唯一的整数 z 之间 0 和 (10^9+6) (含)使得 xz \equiv y \pmod {10^9+7}.
约束
- 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
- 给定的图表很简单。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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 运算,模数 (10^9 + 7),如注释中所述。
示例输入 1
3 2 1 3 1 5 1 2 1 3
示例输出 1
3 500000005 500000008
- 如果边缘 1 在唯一的操作中被选择:写在 Vertices 上的顶点 分别为 1, 2, 3 将是 2, 2, 5。
- 如果边缘 2 在唯一的操作中被选择:写在 Vertices 上的顶点 分别为 1, 2, 3 将是 4, 1, 4。
因此,写在顶点上的数字的期望值 1, 2, 3 是 3, \frac{3}{2}, \frac{9}{2}。
如果我们将它们表示为模 (10^9 + 7) 如注释中所述,它们将是
在中选择 3, 500000005, 500000008。
示例输入 2
3 2 2 12 48 36 1 2 1 3
示例输出 2
750000036 36 250000031
- 如果边缘 1 被选择在 1-st 操作:
写在顶点上的数字 1, 2, 3 将是 30, 30, 36。
- 如果边缘 1 被选择在 2-nd操作: 写在顶点上的数字 1, 2, 3 将是 30, 30, 36。
- 如果边缘 2 被选择在 2-nd操作: 写在顶点上的数字 1, 2, 3 将是 33, 30, 33。
- 如果边缘 2 被选择在 1-st 操作:
写在顶点上的数字 1, 2, 3 将是 24, 48, 24。
- 如果边缘 1 被选择在 2-nd操作: 写在顶点上的数字 1, 2, 3 将是 36, 36, 24。
- 如果边缘 2 被选择在 2-nd操作: 写在顶点上的数字 1, 2, 3 将是 24, 48, 24。
这四种情况都有概率发生 \frac{1}{4},所以写在顶点上的数字的期望值 1, 2, 3 是 \frac{123}{4}, \frac{144}{4} (=36), \frac{117}{4}。
示例输入 3
4 5 1000 578 173 489 910 1 2 2 3 3 4 4 1 1 3
示例输出 3
201113830 45921509 67803140 685163678