← 返回题目列表

AtCoder · abc277_g

G. 随机游走至百万富翁

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

分数: 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. 在第一个动作中,他从顶点移动 1 到相邻顶点,顶点 2。然后,自从 C_2 = 0,他的等级提升至 1.
  2. 在第二个动作中,他从顶点移动 2 到相邻顶点,顶点 4。然后,自从 C_4 = 1,他收到 1^2 = 1 日元。
  3. 在第三个动作中,他从顶点移动 4 到相邻顶点,顶点 5。然后,自从 C_5 = 0,他的等级提升至 2.
  4. 在第四个动作中,他从顶点移动 5 到相邻顶点,顶点 4。然后,自从 C_4 = 1,他收到 2^2 = 4 日元。
  5. 在第五个动作中,他从顶点移动 4 到相邻顶点,顶点 2。然后,自从 C_2 = 0,他的等级提升至 3.
  6. 在第六个动作中,他从顶点移动 2 到相邻顶点,顶点 1。然后,自从 C_1 = 0,他的等级提升至 4.
  7. 在第七个动作中,他从顶点移动 1 到相邻顶点,顶点 2。然后,自从 C_2 = 0,他的等级提升至 5.
  8. 在第八个动作中,他从顶点移动 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