首页 > 其他分享 >题解 [ABC199F] Graph Smoothing(中文/English)

题解 [ABC199F] Graph Smoothing(中文/English)

时间:2024-08-28 11:28:41浏览次数:9  
标签:return Matrix int 题解 Smoothing Graph operator Modint friend

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

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)\).

标签:return,Matrix,int,题解,Smoothing,Graph,operator,Modint,friend
From: https://www.cnblogs.com/ruierqwq/p/18384249/abc199f

相关文章

  • 递推配套P1192 & 题解:P1192 台阶问题
    我们现在考虑递推。现在的问题是,如何从前几个数据推导出下一个数据。我们现在先推导\(f(n)\)。设\(k=3\)。到\(n\)的方法就是到能一步到\(n\)的台阶的方法总和,所以我们可以推导出:\(f(n)=f(n-1)+f(n-2)+\dots+f(n-k)/f(1)\)。即为:\(f(n)=\sum_{i=......
  • LOJ #160. 树形背包 题解
    Description有\(N\)个物品,编号分别为\(1\ldotsN\)。物品\(i\)的重量为\(w_i\),价值为\(v_i\)。给出每个物品依赖于哪个物品。我们用\(d_i=j\(i>j>0)\)表示:如果要选取物品\(i\),就必须先选取物品\(j\)。另外,我们用\(d_i=0(i>0)\)表示:该物品不依赖于任何物品。......
  • CF1810G The Maximum Prefix 题解
    Description构造一个长度最多为\(n\)的数组\(a\),其每个元素均为\(1\)或\(-1\)。生成方式如下:选择任意整数\(k\in[1,n]\)作为\(a\)的长度。对于\(\foralli\in[1,k]\),有\(p_i\)的概率设\(a_i=1\),有\(1-p_i\)的概率设\(a_i=-1\)。在数列被生成后,计算\(s_i=a......
  • NOI2024 D1T3 口胡题解
    NOI2024D1T3口胡题解题目条件其实就是说对于点对\((a,b)\),从\(a\)到\(b\)的路径上至少要有一条从\(b\)指向\(a\)​的边。将初始状态记作\((T,S)\)​,其中\(T\)​是树,\(S\)​是二元组\((a,b)\)​的集合。注意到特殊性质A蕴含了:如果对于所有二元组\((a,b)\),\(a......
  • [COCI2012-2013#1] SNAGA 题解
    前言题目链接:洛谷。题意简述定义\(f(x)\)表示不能整除\(x\)的最小正整数。给出数字\(n\),每次\(n\getsf(n)\),当\(n=2\)时停止。定义\(g(n)\)为这一过程中的数字个数,例如\(g(6)=4\)。给定\(l,r\),求\(\sum\limits_{i=l}^rg(i)\)。\(3\leql\ltr......
  • 【题解】「CQOI2014」通配符匹配
    【题解】「CQOI2014」通配符匹配https://www.luogu.com.cn/problem/P3167令\(s\)为模式串,\(t\)为文本串。首先有一个显然的的dp是,\(f_{i,j}\)表示模式串的前\(i\)个和文本串的前\(j\)个是否匹配。显然\(O(n^2)\)是过不了的。Motivation:注意到题目限定了通配符......
  • CMake构建学习笔记8-OpenSceneGraph库的构建
    1.概论在连续构建了zlib、libpng、libjpeg、libtiff、giflib以及freetype这几个库之后,接下来我们就要来一个大的,构建OpenSceneGraph这样大型库。OpenSceneGraph(简称OSG)是一个高性能、跨平台的三维图形应用程序框架,广泛应用于科学可视化、模拟仿真、游戏开发等领域。理论上来说,......
  • CF645D - Robot Rapping Results Report 题解
    \[Problem\]有\(N\)个机器人,给出\(M\)组关系,表示两个机器人的能力关系,问至少需要前几组关系可以确定所有机器人的排名。\[Solution\]由于是求最少的前几组关系,而关系越少越难确定排名,关系越多越容易确定,不难发现本题满足单调性,考虑二分。那么给出关系要求总排名的题,就应该......
  • AT_code_festival_2017_qualc_d - Yet Another Palindrome Partitioning 题解
    YetAnotherPalindromePartitioning题解题目大意给出一个字符串,求把这个字符串划分成最少的小段,使每个小段都可以经过字母重组后为回文串。题目分析如果暴力的话,需要DFS段数、每一段的左节点、右节点,以及判断是否为回文串,时间复杂度在\(O(|S|^{|S|})\)左右。但是本......
  • Dirsearch-master安装使用及常见问题解决(互联网和内网)
    1、文档概述        本手册适用于帮助初学者快速掌握Dirsearch-master的安装、配置与使用方法。通过阅读本文档,您将能够了解如何搭建Dirsearch-master环境、扫描目标服务器上潜在的敏感文件和目录,并解读生成的报告。此外,本文档还涵盖了常见问题及解决方法,以便您在实际......