102776: [AtCoder]ABC277 G - Random Walk to Millionaire
Description
Score : $600$ points
Problem Statement
You are given a connected simple undirected graph consisting of $N$ vertices and $M$ edges.
For $i = 1, 2, \ldots, M$, the $i$-th edge connects vertex $u_i$ and vertex $v_i$.
Takahashi starts at Level $0$ on vertex $1$, and will perform the following action exactly $K$ times.
- First, choose one of the vertices adjacent to the vertex he is currently on, uniformly at random, and move to the chosen vertex.
- Then, the following happens according to the vertex $v$ he has moved to.
- If $C_v = 0$: Takahashi's Level increases by $1$.
- If $C_v = 1$: Takahashi receives a money of $X^2$ yen, where $X$ is his current Level.
Print the expected value of the total amount of money Takahashi receives during the $K$ actions above, modulo $998244353$ (see Notes).
Notes
It can be proved that the sought expected value is always a rational number. Additionally, under the Constraints of this problem, when that value is represented as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, it can also be proved that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find this $R$.
Constraints
- $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$
- The given graph is connected.
- $C_i \in \lbrace 0, 1\rbrace$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $K$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$ $C_1$ $C_2$ $\ldots$ $C_N$
Output
Print the answer.
Sample Input 1
5 4 8 4 5 2 3 2 4 1 2 0 0 1 1 0
Sample Output 1
89349064
Among the multiple paths that Takahashi may traverse, let us take a case where Takahashi starts on vertex $1$ and goes along the path $1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3$, and compute the total amount of money he receives.
- In the first action, he moves from vertex $1$ to an adjacent vertex, vertex $2$. Then, since $C_2 = 0$, his Level increases to $1$.
- In the second action, he moves from vertex $2$ to an adjacent vertex, vertex $4$. Then, since $C_4 = 1$, he receives $1^2 = 1$ yen.
- In the third action, he moves from vertex $4$ to an adjacent vertex, vertex $5$. Then, since $C_5 = 0$, his Level increases to $2$.
- In the fourth action, he moves from vertex $5$ to an adjacent vertex, vertex $4$. Then, since $C_4 = 1$, he receives $2^2 = 4$ yen.
- In the fifth action, he moves from vertex $4$ to an adjacent vertex, vertex $2$. Then, since $C_2 = 0$, his Level increases to $3$.
- In the sixth action, he moves from vertex $2$ to an adjacent vertex, vertex $1$. Then, since $C_1 = 0$, his Level increases to $4$.
- In the seventh action, he moves from vertex $1$ to an adjacent vertex, vertex $2$. Then, since $C_2 = 0$, his Level increases to $5$.
- In the eighth action, he moves from vertex $2$ to an adjacent vertex, vertex $3$. Then, since $C_3 = 1$, he receives $5^2 = 25$ yen.
Thus, he receives a total of $1 + 4 + 25 = 30$ yen.
Sample Input 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
Sample Output 2
139119094
Input
题意翻译
给出一个 $n$ 个点 $m$ 条边的无向简单连通图,每个点有一个点权 $C_i\in\{0,1\}$。 $\text{Takahashi}$ 初始时在 $1$ 号点,等级为 $0$。接下来他要做 $K$ 次如下操作: - 随机地走向当前所在点的一个相邻点。 - 如果这个点 $C_i=0$,将等级加一;如果这个点 $C_i=1$,设 $\text{Takahashi}$ 当前的等级为 $X$,他可以获得 $X^2$ 元钱。 求 $K$ 次操作中 $\text{Takahashi}$ 一共获得的钱数的期望,答案对 $998244353$ 取模。 $(1\le n,m,K\le 3000)$Output
问题描述
给你一个包含$N$个顶点和$M$条边的简单无向连通图。
对于$i = 1, 2, \ldots, M$,第$i$条边连接顶点$u_i$和顶点$v_i$。
Takahashi 在顶点 1 处从 Level $0$ 开始,将在接下来的 $K$ 次行动中执行以下操作。
- 首先,他随机均匀地从他当前所在顶点的相邻顶点中选择一个,并移动到选择的顶点。
- 然后,根据他移动到的顶点$v$,会发生以下情况:
- 如果$C_v = 0$: Takahashi 的 Level 增加 1。
- 如果$C_v = 1$: Takahashi 收到$X^2$日元的金钱,其中$X$是他的当前 Level。
求 Takahashi 在上述 $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
考虑 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$,他的 Level 增加到 $1$。
- 在第二次行动中,他从顶点 $2$ 移动到相邻顶点,顶点 $4$。然后,由于 $C_4 = 1$,他收到 $1^2 = 1$ 日元。
- 在第三次行动中,他从顶点 $4$ 移动到相邻顶点,顶点 $5$。然后,由于 $C_5 = 0$,他的 Level 增加到 $2$。
- 在第四次行动中,他从顶点 $5$ 移动到相邻顶点,顶点 $4$。然后,由于 $C_4 = 1$,他收到 $2^2 = 4$ 日元。
- 在第五次行动中,他从顶点 $4$ 移动到相邻顶点,顶点 $2$。然后,由于 $C_2 = 0$,他的 Level 增加到 $3$。
- 在第六次行动中,他从顶点 $2$ 移动到相邻顶点,顶点 $1$。然后,由于 $C_1 = 0$,他的 Level 增加到 $4$。
- 在第七次行动中,他从顶点 $1$ 移动到相邻顶点,顶点 $2$。然后,由于 $C_2 = 0$,他的 Level 增加到 $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