AT_abc277_g [ABC277G] Random Walk to Millionaire

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的连通且简单的无向图。
对于 $i = 1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

高桥君一开始处于顶点 $1$，等级为 $0$，然后他会恰好进行 $K$ 次如下操作：

• 首先，从当前所在顶点的所有相邻顶点中，等概率随机选择一个顶点并移动到该顶点。
• 然后，根据移动后的顶点 $v$，会发生如下事件：
  • 如果 $C_v = 0$：高桥君的等级增加 $1$。
  • 如果 $C_v = 1$：设高桥君当前等级为 $X$，他会获得 $X^2$ 日元。

请输出在上述 $K$ 次操作过程中，高桥君获得的金钱总额的期望值，结果对 $998244353$ 取模（见注释）。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $K$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
$C_1$ $C_2$ $\ldots$ $C_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5 4 8
4 5
2 3
2 4
1 2
0 0 1 1 0

输出 #1

89349064

输入输出样例 #2

输入 #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

说明/提示

注释

可以证明，所求的期望值一定是有理数。在本题的约束下，设其为两个互质整数 $P$、$Q$ 的比值 $\frac{P}{Q}$，则存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 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$
• 输入均为整数

样例解释 1

高桥君的移动路径有多种可能，这里以 $1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3$ 为例，计算他获得的金钱总额：

1. 第 1 次操作，从顶点 $1$ 移动到相邻的顶点 $2$。$C_2 = 0$，等级升为 $1$。
2. 第 2 次操作，从顶点 $2$ 移动到相邻的顶点 $4$。$C_4 = 1$，获得 $1^2 = 1$ 日元。
3. 第 3 次操作，从顶点 $4$ 移动到相邻的顶点 $5$。$C_5 = 0$，等级升为 $2$。
4. 第 4 次操作，从顶点 $5$ 移动到相邻的顶点 $4$。$C_4 = 1$，获得 $2^2 = 4$ 日元。
5. 第 5 次操作，从顶点 $4$ 移动到相邻的顶点 $2$。$C_2 = 0$，等级升为 $3$。
6. 第 6 次操作，从顶点 $2$ 移动到相邻的顶点 $1$。$C_1 = 0$，等级升为 $4$。
7. 第 7 次操作，从顶点 $1$ 移动到相邻的顶点 $2$。$C_2 = 0$，等级升为 $5$。
8. 第 8 次操作，从顶点 $2$ 移动到相邻的顶点 $3$。$C_3 = 1$，获得 $5^2 = 25$ 日元。

因此，高桥君获得的金钱总额为 $1 + 4 + 25 = 30$ 日元。

由 ChatGPT 4.1 翻译