题解 P3317 【[SDOI2014]重建】

· · 题解

做法

我们都知道(其实我是刚知道的)，矩阵树求的是：\sum\limits_{T}\prod\limits_{e \in T}p_e

而这题求的是：\sum\limits_{T}(\prod\limits_{e\in T}p_e \prod\limits_{e\notin T} (1-p_e))

通俗地将：枚举每个树，属于这个树边出现的概率×非树边出现的概率

\sum\limits_{T}(\prod\limits_{e\in T}p_e \prod\limits_{e\notin T} (1-p_e)) =\sum\limits_{T}(\prod\limits_{e\in T}p_e \frac{\prod_{e}(1-P_e)}{\prod_{e\in T}(1-P_e)}) =\prod\limits_{e}(1-p_e)(\sum\limits_{T}\prod\limits_{e\in T}\frac{pe}{(1-pe)})

化成标准形式套膜拜就好了

Code