min-max容斥

奇怪的东西呢。

对于集合S,有 (max(S) = sumlimits_{T in S} (-1)^{|T|+1}min(T))

证明应该可以自己感性理解一下。会发现除了最大值都被正负消掉了。

随机游走:

我们求出 dp[x][Y] 表示从 x 到集合 Y 内的任意一个点的期望步数。

要求从 x 经过集合 S 所有点的期望步数。

可以使用min-max容斥。有(ans = sumlimits_{T in S} (-1)^{|T|+1}dp[x][T])

min-max容斥搭配期望使用味道更佳(

原文地址:https://www.cnblogs.com/nao-nao/p/14903008.html