分数: 600 点
问题陈述
给你一个连通的简单无向图,包括 N 顶点和 M 边缘。
对于 i = 1, 2, \ldots, M, i第一条边连接顶点 u_i 和顶点 v_i.
高桥开始于 等级 0 在顶点 1,并将准确执行以下操作 K 次。
- 首先,均匀随机地选择与他当前所在顶点相邻的顶点之一,并移动到所选顶点。
- 然后,根据顶点发生以下情况 v 他已经搬到了。
- If C_v = 0: 高桥的等级增加 1.
- If C_v = 1: 高桥收到一笔钱 X^2 日元,其中 X 是他当前的等级。
打印高桥在该期间收到的总金额的预期值 K 上面的动作,模数 998244353 (见注释)。
注释
可以证明,求的期望值始终是有理数。此外,在该问题的约束下,当该值表示为 \frac{P}{Q} 使用两个互质整数 P 和 Q,也可以证明存在唯一的整数 R 这样 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。找到这个 R.
约束
- 2 \leq N \leq 3000
- N-1 \leq M \leq \min\lbrace N(N-1)/2, 3000\rbrace
- 1 \leq K \leq 3000
- 1 \leq u_i, v_i \leq N
- u_i \neq v_i
- i \neq j \implies \lbrace u_i, v_i\rbrace \neq \lbrace u_j, v_j \rbrace
- 给定的图形已连接。
- C_i \in \lbrace 0, 1\rbrace
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M K u_1 v_1 u_2 v_2 \vdots u_M v_M C_1 C_2 \ldots C_N
输出
打印答案。
示例输入 1
5 4 8 4 5 2 3 2 4 1 2 0 0 1 1 0
示例输出 1
89349064
在高桥可能走过的多条路径中,让我们以高桥从顶点开始的情况为例 1 并沿着路径走 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3,并计算他收到的总金额。
- 在第一个动作中,他从顶点移动 1 到相邻顶点,顶点 2。然后,自从 C_2 = 0,他的等级提升至 1.
- 在第二个动作中,他从顶点移动 2 到相邻顶点,顶点 4。然后,自从 C_4 = 1,他收到 1^2 = 1 日元。
- 在第三个动作中,他从顶点移动 4 到相邻顶点,顶点 5。然后,自从 C_5 = 0,他的等级提升至 2.
- 在第四个动作中,他从顶点移动 5 到相邻顶点,顶点 4。然后,自从 C_4 = 1,他收到 2^2 = 4 日元。
- 在第五个动作中,他从顶点移动 4 到相邻顶点,顶点 2。然后,自从 C_2 = 0,他的等级提升至 3.
- 在第六个动作中,他从顶点移动 2 到相邻顶点,顶点 1。然后,自从 C_1 = 0,他的等级提升至 4.
- 在第七个动作中,他从顶点移动 1 到相邻顶点,顶点 2。然后,自从 C_2 = 0,他的等级提升至 5.
- 在第八个动作中,他从顶点移动 2 到相邻顶点,顶点 3。然后,自从 C_3 = 1,他收到 5^2 = 25 日元。
因此,他总共收到 1 + 4 + 25 = 30 日元。
示例输入 2
8 12 20 7 6 2 6 6 4 2 1 8 5 7 2 7 5 3 7 3 5 1 8 6 3 1 4 0 0 1 1 0 0 0 0
示例输出 2
139119094