min-max 容斥

對于一個長度為 \(n\) 數列 \(\left \{ a_i \right \}\)，有如下式子：

以上計算過程稱作 min-max 容斥，也叫最值反演，證明過程參考的 OI Wiki，把該計算過程用一般的容斥原理表示出來即可證明，考慮構造雙射 \(f(x)=\left \{ 1,2,\cdots ,x \right \}\)，顯然 \(x=\left | f(x)\right |\)，\(\min \left \{ x,y\right \}=\left | f(x) \cap f(y) \right |\)，\(\max \left \{ x,y\right \}=\left | f(x) \cup f(y) \right |\)。于是得到如下式子：

證畢，min 的計算過程的證明與 max 的一樣。

min-max 容斥求解數學期望

前置知識：數學期望具有線性性質

對于兩個變量 \(x\) 和 \(y\)，以及兩個常數 \(a\) 和 \(b\)，有如下線性性質：

因此，min-max 容斥可帶入到期望的計算當中：

前置知識：離散隨機變量的幾何分布

假設一個變量 \(x\) 表示實驗第一次成功的實驗次數，實驗成功的概率為 \(p\)，顯然：

則變量 \(x\) 的數學期望為：

考慮如何化簡此式，我們知道幾何級數：

這個可以由等比數列求和直接求得，該式只在 \(x \in [0,1)\) 成立，因為該式只在 \(x \in [0,1)\) 時收斂，對等式兩邊同時求導，得到如下式子：

代入 \(E(x)\) 得：

問題一

描述：
有 \(n\) 張卡牌，每張卡牌的數字都不一樣，背面都一樣，將所有卡牌背面朝上放在桌子上，從中隨機抽取一張記下其數字，然后放回，需要抽 \(k\) 次卡牌才可以看到所有的數字，求 \(E(k)\)，時間復雜度要求 \(O(n)\)。

思路：
設 \(T_i\) 表示第一次看到第 \(i\) 張卡牌的次數，則有如下：

考慮如何求 \(E(\min_{j \in S} \left \{ T_{j} \right \})\)，\(\min_{j \in S} \left \{ T_{j} \right \}\) 表示第一次抽取到集合 \(S\) 的卡牌的抽取次數，考慮幾何分布，其期望值即為抽到集合 \(S\) 中任意一張卡牌的概率的倒數，如下：

帶入原式，改變枚舉方式，枚舉子集大小，得到如下式子：

化簡到這里已經足夠了，如果你有一定的高等數學基礎，這個式子還可以繼續化簡，就得到了如下式子（不再說明計算過程）：

問題二（[HAOI2015] 按位或）

描述：
有一個變量 \(x\) ，最初 \(x=0\)，接下來每次操作從區間 \([0,2^n-1]\) 當中選擇一個整數，然后 \(x \gets x \operatorname{or} i\)，\(\operatorname{or}\) 表示按位或操作，選擇整數 \(i\) 的概率為 \(p_i\)，需要 \(k\) 次才能使 \(x=2^n-1\)，求 \(E(k)\)，\(n \le 20\)。
思路：
當 \(x=2^n-1\) 時，其二進制形式下的有 \(n\) 位且都是 \(1\)，設 \(T_i\) 表示 \(x\) 在二進制形式下第 \(i\) 位是 \(1\) 的操作次數，\(E(k)\) 表示為如下：

其中 \(E(\min_{j \in S} \left \{ T_{j} \right \})\) 同樣可以由幾何分布得出，如下：

其中 \(f(G)=\sum2^{G_i}\)，即 \(G\) 所表示的原數，這里需要提前預處理出所有集合的子集和，可以考慮 SOS DP，也可以考慮 FMT，最后直接枚舉就行了，時間復雜度為 \(O(n2^n)\)。