BZOJ 3534 [Sdoi2014] 重建

发布于 2017-09-19  245 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3534

题意:给出矩阵 G,其中\(G_{i,j}\) 表示连接 i-j 的边存在的概率,求这个图是一个原图生成树的概率。


约定

记 T 是一个生成树的边集。


朴素的想法是直接跑高斯消元,得出的是这个东西:\(\sum_{T}^{ }\prod_{e\in T}^{ }G_e\)

考虑真正需要求的是什么:\(ans=\sum_{T}^{ }\prod_{e\in T}^{ }G_e\prod_{e\notin T}^{ }(1-G_e)\)

所以直接用 G 跑高斯消元是不行的,于是构造矩阵 P,其中\(P_e=\frac{G_e}{1-G_e}\)

对 P 跑高斯消元,代回原式,可得:\(sum=\sum_{T}^{ }\prod_{e\in T}^{ }\frac{G_e}{1-G_e}\)

构造辅助项 tmp,其中\(tmp=\prod (1-G_e)\)

\(sum*tmp=\sum_{T}^{ }\prod_{e\in T}^{ }\frac{G_e}{1-G_e}*\prod (1-G_e)\)

整理一下,可以发现,对于\(e\in T\) 的边,对答案的贡献恰为\(G_e\),对于\(e\notin T\) 的边,对答案的贡献恰为\(1-G_e\)

所以\(ans=sum*tmp\),随便高斯消元好了。

有一些细节的处理。

 

 


一个非常弱的准退役OIER