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.

last update: