F - Graph Smoothing 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

N 頂点 M 辺の単純無向グラフがあります。頂点には 1 から N までの、辺には 1 から M までの番号がついています。
辺 i は頂点 X_i と頂点 Y_i を結んでいます。また、頂点 i には最初整数 A_i が書かれています。
あなたは K 回にわたって以下の操作を行います。

  • M 本ある辺の中から、一様ランダムかつ他の選択と独立に 1 本選ぶ。その辺が結ぶ 2 頂点に書かれている数の平均を x として、その 2 頂点に書かれている数を両方 x で置き換える。

各頂点 i について、K 回の操作後に頂点 i に書かれている数の期待値を求め、注記の通り \bmod (10^9 + 7) で出力してください。

注記

有理数を出力する際は、まずその有理数を分数 \frac{y}{x} として表してください。
ここで、x,y は整数であり、x は 10^9+7 で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。
そして、xz \equiv y \pmod {10^9+7} を満たすような 0 以上 10^9+6 以下の唯一の整数 z を出力してください。

制約

  • 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 回の操作後に頂点 i に書かれている数の期待値を、注記に従って \bmod (10^9 + 7) で出力せよ。

入力例 1

3 2 1
3 1 5
1 2
1 3

出力例 1

3
500000005
500000008
  • 唯一の操作で辺 1 が選ばれた場合 : 頂点 1, 2, 3 に書かれている数はそれぞれ 2, 2, 5 となります
  • 唯一の操作で辺 2 が選ばれた場合 : 頂点 1, 2, 3 に書かれている数はそれぞれ 4, 1, 4 となります

従って、操作後に頂点 1, 2, 3 に書かれている数の期待値はそれぞれ 3, \frac{3}{2}, \frac{9}{2} となります。
これらを注記に従って \bmod (10^9 + 7) の表現に変換すると、それぞれ 3, 500000005, 500000008 となります。

入力例 2

3 2 2
12 48 36
1 2
1 3

出力例 2

750000036
36
250000031
  • 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} となります。

入力例 3

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

出力例 3

201113830
45921509
67803140
685163678

Score : 600 points

Problem Statement

We have a simple undirected graph with N vertices and M edges. The vertices are numbered 1 through N and the edges are numbered 1 through M.
Edge i connects Vertex X_i and Vertex Y_i. Initially, Vertex i has an integer A_i written on it.
You will do the following operation K times:

  • Choose one from the M edges uniformly at random and independently from other choices. Let x be the arithmetic mean of the numbers written on the two vertices connected by that edge. Replace each number written on those vertices with x.

For each vertex i, find the expected value of the number written on that vertex after K operations, and print it modulo (10^9 + 7) as described in Notes.

Notes

When printing a rational number, first, represent it as a fraction \frac{y}{x}, where x and y are integers and x is not divisible by (10^9+7) (under the Constraints of this problem, such a representation is always possible).
Then, print the only integer z between 0 and (10^9+6) (inclusive) such that xz \equiv y \pmod {10^9+7}.

Constraints

  • 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
  • The given graph is simple.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print N lines.
The i-th line should contain the expected value of the number written on that vertex after K operations, modulo (10^9 + 7), as described in Notes.

Sample Input 1

3 2 1
3 1 5
1 2
1 3

Sample Output 1

3
500000005
500000008
  • If Edge 1 is chosen in the only operation: the vertices written on Vertices 1, 2, 3 will be 2, 2, 5, respectively.
  • If Edge 2 is chosen in the only operation: the vertices written on Vertices 1, 2, 3 will be 4, 1, 4, respectively.

Thus, the expected values of the numbers written on Vertices 1, 2, 3 are 3, \frac{3}{2}, \frac{9}{2}, respectively.
If we express them modulo (10^9 + 7) as described in Notes, they will be 3, 500000005, 500000008, respectively.

Sample Input 2

3 2 2
12 48 36
1 2
1 3

Sample Output 2

750000036
36
250000031
  • If Edge 1 is chosen in the 1-st operation: The numbers written on Vertices 1, 2, 3 will be 30, 30, 36, respectively.
    • If Edge 1 is chosen in the 2-nd operation: The numbers written on Vertices 1, 2, 3 will be 30, 30, 36, respectively.
    • If Edge 2 is chosen in the 2-nd operation: The numbers written on Vertices 1, 2, 3 will be 33, 30, 33, respectively.
  • If Edge 2 is chosen in the 1-st operation: The numbers written on Vertices 1, 2, 3 will be 24, 48, 24, respectively.
    • If Edge 1 is chosen in the 2-nd operation: The numbers written on Vertices 1, 2, 3 will be 36, 36, 24, respectively.
    • If Edge 2 is chosen in the 2-nd operation: The numbers written on Vertices 1, 2, 3 will be 24, 48, 24, respectively.

Each of these four scenarios happen with probability \frac{1}{4}, so the expected values of the numbers written on Vertices 1, 2, 3 are \frac{123}{4}, \frac{144}{4} (=36), \frac{117}{4}, respectively.

Sample Input 3

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

Sample Output 3

201113830
45921509
67803140
685163678