Random Walk to Millionaire

题目描述

你被给定一个由 $N$ 个顶点和 $M$ 条边组成的连通简单无向图。
对于 $i = 1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 Takahashi 从顶点 $1$ 的 等级 $0$ 开始，将恰好执行以下动作 $K$ 次。

首先，从他当前所在的顶点的若干相邻顶点中均匀随机选择一个顶点，并移动到所选择的顶点。 然后，根据他移动到的顶点 $v$ 发生如下情况。 如果 $C_v = 0$：Takahashi 的等级增加 $1$。 如果 $C_v = 1$：Takahashi 收到 $X^2$ 日元的金钱，其中 $X$ 是他当前的等级。

输出在上述 $K$ 次动作中 Takahashi 收到的金钱总额的期望值，对 $998244353$ 取模（参见说明）。

输入格式

输入由标准输入按以下格式给出： $N$ $M$ $K$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$ $C_1$ $C_2$ $\ldots$ $C_N$

输出格式

输出答案。

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

89349064

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

139119094

提示

$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$ 输入中的所有数值均为整数。可以证明所求的期望值总是一个有理数。此外，在本题的约束下，当该值表示为互素整数 $P$ 和 $Q$ 的分数 $\frac{P}{Q}$ 时，也可以证明存在唯一整数 $R$ 使得 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。求该 $R$。在 Takahashi 可能经过的多条路径中，取这样一种情况：Takahashi 从顶点 $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$ 日元。

标签: AtCoder|abc277G

来源

AtCoder|abc277G