Min-Max容斥

Min-Max容斥,也叫最值反演(脑子不够,套路来凑),可以处理一些计数问题。

形式(公式挂光了,救救孩子):

Max(S) = \sum_{T \subseteq S} (-1)^(|T| + 1) Min(T)

Min(S) = \sum_{T \subseteq S} (-1)^(|T| + 1) Max(T)

 

本质上是容斥TAT,用反演的角度来看,就是只有当T的size为1且是最大值时才会被计入贡献(等式咕了

这里的Min与Max并一定要是最大值和最小值,只要是在某一种偏序下的两个极端就好了。

基本上的套路大概就是随机选一段子集染色,问期望多久把全集染满——这是Max,就可以转化成对于每一个子集,期望第一次被染色的时间的值——这是Min。

 

好像还有GCD和LCM的转化,待填。

发表评论

电子邮件地址不会被公开。 必填项已用*标注