← 返回题目列表

AtCoder · abc199_f

F. 图形平滑

中文机器翻译题面 查看原题

分数: 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