Random Walk

TimeLimit:9000MS MemoryLimit:262144KB

64-bit integer IO format:%I64d

未提交 | 登录后收藏

Problem Description

Give you an undirected simple graph with $n$ vertices and $m$ edges and there are $a_i$ coins on the $i$th edge. Kris will randomly choose a starting vertex $s (1 \leq s < n)$ and each second he will uniformly randomly walk to another adjacent vertex until reach the vertex $n$. The coins on edges will decay to a half per second but no less than $b_i$, formally if Kris walk through the $i$th edge at $t (t \geq 1)$ second, he will collect $max\{\lfloor \frac{a_i}{2^{t-1}} \rfloor, b_i\}$ coins. The graph will vary over time, after each change you should answer the expected coins he will collect. It is guaranteed that the graph is connected.

Input

This problem only contains one test case.

The first line of the input contains three integers $n, m, q (2 \leq n \leq 500, 1 \leq m \leq 10^4, 1 \leq q \leq 10^6)$. The next line contains $n - 1$ integers $w_i (1 \leq w_i \leq 10^4)$. The probability of vertex $x$ as the starting vertex can be represented as follow:
\begin{equation}
P_x = \frac{w_x}{\sum_{i=1}^{n-1}w_i} \tag{1}
\end{equation}
The next $m$ lines contains four integers $x, y, a, b (1 \leq x, y \leq n, 1 \leq b \leq a \leq 100)$, representing an edge between $x$ and $y$ with $a$ coins initially and $b$ coins finally.

Then $q$ lines follow, each line has one of the following format:

1 x y a b $(1 \leq x, y \leq n, 1 \leq b \leq a \leq 100)$, representing changing the initial coins on $(x, y)$ to $a$ and final coins on $(x, y)$ to $b$. It is guaranteed that there is an edge between $x$ and $y$.

2 x c $(1 \leq x \leq n - 1, 1 \leq c \leq 10^4)$, representing changing $w_x$ to $c$. Note that after this change not only $P_x$ but all probabilities will change according to formula (1). It is guaranteed that the number of this change is no more than $n$.

Note that the changes are persistent and the $(i+1)$th change is based on the $i$th change.

Output

Before the first change and after each change, output the expected coins Kris will collect. Assume that the answer is $\frac{P}{Q}$, then you should output $P \cdot Q^{-1} \mod 998244353$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo 998244353.

Notes:

After Kris collect coins on an edge, the coins on it will not vanish. When he visit the edge the second time, he will collect coins on it again but the number may change.

At the very begin, the expected coins which Kris will collect for starting vertices $1, 2, 3$ are $9$ coins, $8$ coins, $5$ coins respectively, so the answer is $9 \times \frac{1}{3} + 8 \times \frac{1}{3} + 5 \times \frac{1}{3} = \frac{22}{3}$.

SampleInput

SampleOutput

Submit

题目统计信息详细


总AC数	0
通过人数	0
尝试人数	0
总提交量	0
AC率	0.00%

标签——4345

AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题，请不要查看标签
如果您已经通过了该题，请务为该题贴上标签

出处

2021ccpc网络赛

Random Walk

T^T Online Judge