题解 [ABC199F] Graph Smoothing（中文/English）

· · 题解

本题解提供英文版，位于示例代码之后。

English version of this editorial is provided after the sample code.

设行向量：

A^{(k)}= \begin{bmatrix} a_1^{(k)} & a_2^{(k)} & \cdots & a_n^{(k)} \end{bmatrix}

表示 k 次操作后每个节点点权的期望。特别地，A^{(0)} 表示初始时每个节点的点权。我们希望找出 A^{(k)} 间的递推关系 A^{(k)}=A^{(k-1)}M，利用矩阵快速幂解决问题。

设 d_u 表示节点 u 的度数。一轮操作中，u 作为被选中的边的两个端点之一的概率为 \frac{d_u}{m}，此时节点 u 的点权被与另一端点的点权取平均，否则节点 u 的点权不变。因此，有 M_{u,u}=1-\frac{d_u}{2m}。考察与 u 邻接的每个点 v，被选中的边恰为 (u,v) 的概率为 \frac{1}{m}，此时由于取平均，u 点权的一半被贡献给 v。因此，有 M_{u,v}=\frac{1}{2m}。

已知 A^{(0)} 和 M，容易通过矩阵快速幂求出 A^{(k)}，即可得到答案。

时间复杂度 O(n^3\log k)。

示例代码 / Sample code:

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
    return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
    unsigned int x;
    Modint() = default;
    Modint(unsigned int x) : x(x) {}
    friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
    friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
    friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
    friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
    friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
    friend Modint operator/(Modint a, Modint b) {return a * ~b;}
    friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
    friend Modint operator~(Modint a) {return a ^ (mod - 2);}
    friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
    friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
    friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
    friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
    friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
    friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
    friend Modint& operator++(Modint& a) {return a += 1;}
    friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
    friend Modint& operator--(Modint& a) {return a -= 1;}
    friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
    friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
    friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const int N = 105, mod = 1e9 + 7;
typedef Modint<mod> mint;

int n, m, k;
mint a[N], deg[N];
vector<int> e[N];

struct Matrix {
    mint mat[N][N];
    Matrix() {rep(i, 1, n) rep(j, 1, n) mat[i][j] = 0;}
    friend Matrix operator*(const Matrix& a, const Matrix& b) {
        Matrix c;
        rep(i, 1, n) rep(j, 1, n) rep(k, 1, n) c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
        return c;
    }
    friend Matrix& operator*=(Matrix& a, const Matrix& b) {
        return a = a * b;
    }
    friend Matrix operator^(Matrix a, int k) {
        Matrix r;
        rep(i, 1, n) r.mat[i][i] = 1;
        for(; k; k >>= 1, a *= a) if(k & 1) r *= a;
        return r;
    }
    friend Matrix& operator^=(Matrix& a, int k) {
        return a = a ^ k;
    }
}M;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    rep(u, 1, n) cin >> a[u];
    rep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        ++deg[u]; ++deg[v];
        e[u].push_back(v);
        e[v].push_back(u);
    }
    rep(u, 1, n) {
        M.mat[u][u] = 1 - deg[u] / (m * 2);
        for(int v : e[u]) M.mat[u][v] = ~mint(m * 2);
    }
    M ^= k;
    rep(v, 1, n) {
        mint ans = 0;
        rep(u, 1, n) ans += a[u] * M.mat[u][v];
        cout << ans << endl;
    }
    return 0;
}

Let the row vector be defined as:

A^{(k)}= \begin{bmatrix} a_1^{(k)} & a_2^{(k)} & \cdots & a_n^{(k)} \end{bmatrix}

where A^{(k)} represents the expected value of each vertex's weight after k operations. Specifically, A^{(0)} represents the initial weights of each vertex. We aim to find the recurrence relation between A^{(k)} and A^{(k-1)} such that A^{(k)}=A^{(k-1)}M, and solve the problem using matrix exponentiation.

Let d_u denote the degree of vertex u. During one operation, the probability that the selected edge is adjacent to vertex u is \frac{d_u}{m}. In this case, the weight of vertex u is averaged with that of the other vertex connected by the edge; otherwise, the weight of vertex u remains unchanged. Therefore, we have M_{u,u}=1-\frac{d_u}{2m}. Now, consider each adjacent vertex v of u. The probability that the selected edge is exactly (u,v) is \frac{1}{m}, and in this case, half of u's weight is contributed to v due to averaging. Therefore, we have M_{u,v}=\frac{1}{2m}.

Given A^{(0)} and M, A^{(k)} can be easily computed using matrix exponentiation, thus yielding the answer.

The time complexity is O(n^3\log k).