| Online Judge | Online Exercise | Online Teaching | Online Contests | Exercise Author |
|
F.A.Q Hand In Hand Online Acmers |
Best Coder beta VIP | STD Contests DIY | Web-DIY beta |
Random Walk
Time Limit: 15000/9000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 65 Accepted Submission(s): 18
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:
Note that the changes are persistent and the $(i+1)$th change is based on the $i$th change.
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:
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}$.
Sample Input
4 3 3 1 1 1 1 2 1 1 2 3 1 1 3 4 1 1 1 1 2 2 1 2 1 2 1 2 3 4 2
Sample Output
332748125 831870302 623902729 374341644
Source
| Home | Top |
Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-05-17 05:31:02, Gzip enabled |
Administration |