今天真摆了。
昨天晚上打 CF 给我打虚了,今天状态不行。
上午又写了写傻逼期望。下午打了那个傻逼模拟赛。
T1 20 分钟切了,T2 发现题面太长,跳了。T3 搞了半天的输入然后发现 \(1e18\) 随便跑就走了。T4 一眼部分分直接开始打大模拟,过河卒经典了。然后 T2 又搞了一个小时搞出来了,最后喜提 \(0pts\),没输出操作数???
最后 \(100+0+100+66=266pts\),被高一学长暴打了???
戴老师看看你的???
被骂了?
下课时的你画我猜精选
推歌:Ai Drew -Feryquitous
Fery 的歌总有一种空灵的感觉,不仅这首,Arcahv 也有这种感觉。
P3317
矩阵树定理其实求的是这么个玩意:
\[\sum_{T\in Tree}\prod_{e\in T} w_e
\]
但是这题我们要求的东西是这个玩意:
\[\sum_{T\in Tree}\prod_{e\in T} p_e\prod_{e\not \in T}(1-p_e)
\]
我们可以把后面的式子化开:
\[\begin{aligned}
\sum_{T\in Tree}\prod_{e\in T} p_e\prod_{e\not \in T}(1-p_e)&=\sum_{T\in Tree}\prod_{e\in T} p_e\frac{\prod_{e}(1-p_e)}{\prod_{e\in T}(1-p_e)}\\
&=\prod_{e}(1-p_e)\sum_{T}\prod_{e\in T}\frac{p_e}{1-p_e}
\end{aligned}
\]
我们可以把每条边的边权弄成 \(\frac{p_e}{1-p_e}\),然后矩阵树定理即可。
时间复杂度 \(O(n^3)\)。
图图: