Contest Duration: - (local time) (100 minutes) Back to Home

## F - Graph Smoothing Editorial by en_translator

Let $$y_i$$ be the expected value of the number written on vertex $$i$$ after a single operation, before which each vertex $$i$$ has $$x_i$$ written on it.

Then, there exist an matrix $$m$$ such that $$xm = y$$, or equivalently $$\displaystyle y_i = \sum_{j = 1}^N x_j m_{j, i}$$.
Specifically, $$m$$ can be constructed as follows.

• Initially each element of $$m$$ is $$0$$
• Consider each vertex $$i$$. Let $$d_i$$ be the degree of vertex $$i$$ and $$a_{i, 1}, a_{i, 2}, \dots, a_{i, d_i}$$ be the adjacent vertices.
• At the probability of $$\frac{d_i}{M}$$, an edge adjacent to vertex $$i$$ is chosen. In such case the contribution of $$x_i$$ to $$y_i$$ decreases from $$1$$ to $$\frac{1}{2}$$, so $$m_{i, i} = 1 - \frac{d_i}{M} \times \frac{1}{2}$$.
• Also, when an edge connecting $$a_{i, j}$$ and $$i$$ is chosen (at the probability of $$\frac{1}{M}$$, $$x_{a_{i, j}}$$ contribute to $$y_i$$ at the ratio of $$\frac{1}{2}$$, so we let $$m_{a_{i, j}, i} = \frac{1}{2M}$$.

Since the answer for the problem is $$Am^K$$, we can calculate $$m^K$$ with fast exponentiation so that the problem is solved in a total of $$O(N^3 \log(K))$$ time.

posted:
last update: