前言

見到一道神題，學(xué)會(huì)兩個(gè)知識(shí)點(diǎn)…
都是數(shù)學(xué)。

min-max容斥

給出式子：
$$\max (S)=\sum _{T?S}(?1{)}^{|T|}\min (T)$$
$$\min (S)=\sum _{T?S}(?1{)}^{|T|}\max (T)$$
這里只給出第一個(gè)式子的證明，第二個(gè)式子的證明較為類似。
考慮最大值 $\max (S)$，它成為最小值產(chǎn)生貢獻(xiàn)當(dāng)且近當(dāng) $T=\{\max (S)\}$，顯然只會(huì)產(chǎn)生一次正貢獻(xiàn)。
而對(duì)于不是最大值的元素 $x\in S$，設(shè)比它大的元素的個(gè)數(shù)為 $k$，那么它成為最小值產(chǎn)生貢獻(xiàn)當(dāng)且近當(dāng) $T$ 為前 $k$ 個(gè)元素的某個(gè)子集并上 $\{x\}$，那么它的系數(shù)就是：
$$\sum _{i=0}^x\left(\genfrac{}{}{0ex}{}{x}{i}\right)(?1{)}^i$$
二項(xiàng)式反演一下：
$$\sum _{i=0}^x\left(\genfrac{}{}{0ex}{}{x}{i}\right)(?1{)}^i=\sum _{i=0}^x(\genfrac{}{}{0ex}{}{x}{i})(?1{)}^i(1{)}^{x?i}=(1?1{)}^x=0$$
所以所有不是最大值的元素的貢獻(xiàn)都是0。
那么最后西格瑪?shù)慕Y(jié)果就是 $\max (S)$。

注意：這個(gè)式子當(dāng)最小值不唯一的時(shí)候依然成立，$\min (T)$ 的含義就變?yōu)榱怂胁⒘凶钚≈档暮汀５?strong>所求的最大值必須唯一！

期望

這個(gè)東西對(duì)于期望依然是成立的，也就是：
$$E(\max (S))=\sum _{T?S}(?1{)}^{|T|}E(\min (T))$$
$$E(\min (S))=\sum _{T?S}(?1{)}^{|T|}E(\max (T))$$
把定義從元素大小的求值改為期望的求值，完全不影響上面的證明過程，所以還是對(duì)的。

拓展：kth_max

$$\max (S{)}_{kth}=\sum _{T?S}(\genfrac{}{}{0ex}{}{|T|?1}{k?1})(?1{)}^{|T|?k}\min (T)$$
并不會(huì)證
還是挺好記的，$k=1$的時(shí)候就退化成正常的min-max容斥了。

離散隨機(jī)變量的幾何分布

離散變量：值域不連續(xù)的變量。比如我們最常見的“求期望次數(shù)”，值域就是自然數(shù)。

給出一個(gè)離散變量 $x$，其分布概率滿足：
$$P(x=k)=(1?p{)}^{k?1}p$$
其中 $p$ 是一個(gè) $[0,1]$ 的常量。
可以把 $p$ 理解成做成某件事的概率，那么 $P(x=k)$ 就是恰好用 $k$ 次做成這件事的概率。

證明一

現(xiàn)在求這個(gè)變量的期望，也就是：
$$\sum _{i=1}^{\infty }P(x=i)i$$
設(shè) $q=1?p$，那么我們就要求：
$$\sum _{i=1}^{\infty }i\times q^{i?1}\times (1?q)=(1?q)\sum _{i=1}^{\infty }i\times q^{i?1}$$
設(shè) $s={\sum }_{i=1}^{\infty }i\times q^{i?1}$，則有：
$$qs?s=\sum _{i=1}^{\infty }(i\times q^i)?\sum _{i=1}^{\infty }(i\times q^{i?1})$$
$$=\sum _{i=2}^{\infty }((i?1)\times q^{i?1})?\sum _{i=1}^{\infty }(i\times q^{i?1})=?\sum _{i=1}^{\infty }{q}^{i?1}=?\frac{1}{1?q}$$
所以
$$s=?\frac{1}{(1?q)(q?1)}$$
所以原式就是：
$$\sum _{i=1}^{\infty }i\times q^{i?1}\times (1?q)=(1?q)s=?\frac{1}{q?1}=\frac{1}{p}$$

證明二

還有一種更加陽間的證明方法：
回到現(xiàn)實(shí)意義：$w$ 表示做成該件事的期望次數(shù)。
考慮做一次做成或者做不成，就有：
$$w=p\times 1+(1?p)\times (w+1)$$
移項(xiàng)，得：
$$w=\frac{1}{p}$$

總結(jié)

以上是生活随笔為你收集整理的模板：min-max容斥离散随机变量的几何分布（洛谷P3175：[HAOI2015]按位或）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。