AT_abc199_f [ABC199F] Graph Smoothing

题目描述

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

• 从 $M$ 条边中，等概率且相互独立地随机选择一条边。记该边连接的两个顶点上写的数的平均值为 $x$，然后将这两个顶点上的数都替换为 $x$。

请你求出每个顶点 $i$ 在 $K$ 次操作后所写数字的期望值，并按照注释中的要求对 $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$
$\vdots$
$X_M$ $Y_M$

输出格式

请输出 $N$ 行。
第 $i$ 行输出第 $i$ 个顶点在 $K$ 次操作后所写数字的期望值，按照注释中的要求对 $10^9+7$ 取模输出。

输入输出样例 #1

输入 #1

3 2 1
3 1 5
1 2
1 3

输出 #1

3
500000005
500000008

输入输出样例 #2

输入 #2

3 2 2
12 48 36
1 2
1 3

输出 #2

750000036
36
250000031

输入输出样例 #3

输入 #3

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

输出 #3

201113830
45921509
67803140
685163678

说明/提示

注释

输出有理数时，首先将其表示为分数 $\frac{y}{x}$，其中 $x, y$ 为整数，且 $x$ 不能被 $10^9+7$ 整除（在本题的约束下总能做到）。
然后，输出唯一满足 $0 \leq z \leq 10^9+6$ 且 $xz \equiv y \pmod{10^9+7}$ 的整数 $z$。

约束条件

• $2 \leq N \leq 100$
• $1 \leq M \leq \frac{N(N-1)}{2}$
• $0 \leq K \leq 10^9$
• $0 \leq A_i \leq 10^9$
• $1 \leq X_i \leq N$
• $1 \leq Y_i \leq N$
• 给定的图是简单图
• 输入中的所有值均为整数

样例解释 1

• 若唯一的一次操作选择了第 $1$ 条边：顶点 $1, 2, 3$ 上的数分别变为 $2, 2, 5$
• 若唯一的一次操作选择了第 $2$ 条边：顶点 $1, 2, 3$ 上的数分别变为 $4, 1, 4$
  因此，操作后顶点 $1, 2, 3$ 上的数的期望值分别为 $3, \frac{3}{2}, \frac{9}{2}$。
  将其按注释中的方式转化为 $10^9+7$ 下的表达，分别为 $3, 500000005, 500000008$。

样例解释 2

• 第 $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$ 这 $4$ 种情况各以 $\frac{1}{4}$ 的概率发生，因此最终顶点 $1, 2, 3$ 上的数的期望值分别为 $\frac{123}{4}, \frac{144}{4}(=36), \frac{117}{4}$。

由 ChatGPT 4.1 翻译