[R48F]分配权值 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个包含 $n$ 个点和 $m$ 条边的简单无向图。每个点 $i$ 初始时拥有一个整数权值 $a_i$。

每一秒，图中所有的点会同时执行一次权值分发操作： 每个点 $u$ 会将其当前拥有的权值 $W_u$ 平均分配给它所有的邻居。如果点 $u$ 的度数为 $d_u$，则它的每一个邻居都会在这一秒接收到来自 $u$ 的 $\frac{W_u}{d_u}$ 的权值。

请你计算在 $k$ 秒后，每个点上的权值对 $998244353$ 取模后的结果。

由于点权可能是一个分数，设 $P = 998244353$，一个最简分数 $\frac{p}{q}$ 应输出 $p \times q^{P-2} \bmod{P}$。

格式

输入格式

第一行包含三个整数 $n, m, k$，分别表示点数、边数和经过的时间。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个点初始的权值。

接下来 $m$ 行，每行两个整数 $u, v$，表示点 $u$ 和点 $v$ 之间有一条无向边。

输出格式

输出一行 $n$ 个整数，表示 $k$ 秒后每个点权值对 $998244353$ 取模的结果。

样例

样例输入 #1

2 1 1
10 0
1 2

样例输出 #1

0 10

样例解释 #1

• 第 $0$ 秒：点 $1$ 权值为 $10$，点 $2$ 权值为 $0$。
• 点 $1$ 的度数为 $1$，点 $2$ 的度数为 $1$。
• 第 $1$ 秒：点 $1$ 将 $10$ 分给点 $2$；点 $2$ 将 $0$ 分给点 $1$。
• 最终点 $1$ 权值为 $0$，点 $2$ 权值为 $10$。

样例输入 #2

3 2 2
10 0 0
1 2
2 3

样例输出 #2

5 0 5

数据规模

对于 $30\%$ 的数据，$k \leq 1000$。

对于 $100\%$ 的数据，$2 \le n \le 50$，$n - 1 \le m \le \frac{n(n-1)}{2}$，$1 \le k \le 10^{18}$，$0 \le a_i < 998244353$，图无自环，且每个点的度数至少为 $1$。