广告 : 炫酷反演魔术
这个东西看起来挺冷门的，不过要是考的话到不会还真做不出来……
这东西也不是很复杂，本文应该不会太长吧……
我们现在有一个全集 U=\{a_1,a_2,a_3,...,a_n\}
我们设 \large{\min(S)=\min\limits_{a_i∈S}a_i}(集合里的最小值)
相应的 \large{\max(S)=\max\limits_{a_i∈S}a_i}(集合里的最大值)
假设我们能很轻松地求出任意集合的 \min(S) ，但是我们不会(或者很难)求出任意集合的 \max(S) 。
Min-Max容斥就是通过一种奥妙重重的方式把,Min转换成Max(或者反之)。
结论：
\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}\min(T)
为什么是正确的呢？
我们设 U 以内的元素互不相同，如果相同的话我们就以编号为序，不影响后续推导。
我们设 A_k 为 U 内元素降序排序后排名第 k 的元素,也就是第 k 大。
设 \min(S)=A_k 那么 S 有那些情况呢？
1）k=1
我们想得到的就是A_1。
令 \min(S)=A_1，很明显只有一种可能那就是S=\{A_1\}
所以贡献是(-1)^{2}A_1=A_1
2）k>1
最小的元素是 A_k ，那么集合内不能存在比 A_k 小的 A_{k+1...n} ,而只能存在 A_{1...k} 。
通过人类智慧得知，这$2^{k-1}$种选法之中，有$2^{k-2}$种$|S|$是偶数，有$2^{k-2}$种$|S|$是奇数。
那么偶数的情况乘以$-1$，奇数的情况乘以$1$，刚好消掉了。
贡献为 $0
综上，除了\min(S)=\max(S)的那一个S,其余的贡献都消掉了。最后，贡献和是\max(S)。
当然也可以把 \max 转换成 \min ,公式是 \min(S)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}\max(T) ,十分对称。
附：Min-Max容斥定理在期望下也成立。
也就是说 E(\max(S))=\sum\limits_{T\subseteq S}(-1)^{|T|+1}E(\min(T))
这是非常有用的，因为期望下的 \max 和 \min 是很难求的。
假设有 a,b 两个不相关变量，则 E(\max(a,b))≠\max(E(a),E(b))。
例子：抛硬币， a=b=\begin{cases}0(50\%)
\\ 1(50\%)\end{cases} ,则 E(a)=E(b)=\dfrac{1}{2}
那么 \max(a,b)=\begin{cases}\max(0,0)(25\%)\\ \max(0,1)(25\%)\\ \max(1,0)(25\%)\\ \max(1,1)(25\%)\end{cases} ,则 E(\max(a,b))=0.75
但是\max(E(a),E(b))=0.5所以期望不能大力拆 \max 或 \min 。
第一眼看去很难把这道题和Min-Max容斥联想起来（目前而言）
由于或运算时每个位都是独立的，我们可以把每个位分开来看。
我们设a_k为第k个二进制位变为1的时间。
那么我们要求的就是E(\max(U))（U为全集）。
如何求出E(\min(S))呢？
离散期望计算公式E(x)=\sum v*P(v)，意思就是(\sum值*对应概率)。
我们设P(S)为选中集合S的概率，P'(S)为选中S的子集的概率。(U为全集)
那么\min(S)=k的概率就是：前k-1次选了S的补集的子集，最后一次不能选S的补集的子集。
得到\min(S)'s\ P(k)=P'(S⊕U)^{k-1}(1-P'(S⊕U))
那么，E(\min(S))=\sum\limits_{k=1}^∞k*P(k)=\sum\limits_{k=1}^∞k*P'(S⊕U)^{k-1}(1-P'(S⊕U))
设P'(S⊕U)=p
=(1-p)\sum\limits_{k=1}^∞k*p^{k-1}
后面的式子就是等差*等比求和，错位相减：
A=[1*1,2*p,3*p^2...k*p^{k-1}...],$求$Sum
Sum=1*p^0+2*p^1+3*p^2+...
整体乘p得到：p*Sum=1*p+2*p+3*p+...
两式相减得到: (1-p)Sum=1*p^0+(2-1)p+(3-2)p^2+...=\dfrac{1-p^{∞}}{1-p}
因为 0\leq p<1 ,所以 p^∞=0 ,得到 (1-p)Sum=\dfrac{1}{1-p}
所以 E(\min(S))=\dfrac{1}{1-P'(S⊕U)}
我们的目标是要求出 E(\min(\text{所有集合})) ,为了完成这个，我们要求出 P'(\text{所有集合}) 。
我们知道 P'(S)=\sum\limits_{T\subseteq S}P(T) ,肉眼可见枚举子集。
$Or$ 卷积的 $DWT$ 相当于子集求和,那么直接上就好了。
```cpp
#include<algorithm>
#include<cstdio>
#define Maxn 1100000
using namespace std;
int n;
double a[Maxn];
int siz[Maxn];
int main()
{
scanf("%d",&n);n=(1<<n);
for (int i=0;i<n;i++)scanf("%lf",&a[i]);
for (int len=1;len<n;len<<=1)
for (int p=0;p<n;p+=len+len)
for (int i=p;i<p+len;i++)
a[i+len]+=a[i];
double ans=0;
for (int i=1;i<n;i++){
siz[i]=siz[i>>1]+(i&1);
double sav=(1-a[i^(n-1)]);
if (sav<1e-8){puts("INF");return 0;}
sav=1/sav;
ans+=(siz[i]&1) ? -sav:sav;
}printf("%.10lf",-ans);
return 0;
}
```
- **扩展形式**
如果要求第$k$大呢?那怎么办?
我们仍然考虑使用容斥(消去)的方法:
$Kth\!\max(S)=\sum\limits_{T\subseteq S}F(|T|)\min(T)
仿照上面的证明方法来构造:
设一个元素$x$排名为第$p$大,
那么有只有不包含比它小的$n-p+1$个元素时,$\min(T)=x$,有$p-1$个元素可供随意选择,而且必然选择$x$。
贡献系数是$\sum\limits_{i=1}^{p-1}\dbinom{p-1}{i}F(i+1)$。
我们要令这个$=[p=k]$,也就是$\sum\limits_{i=1}^{p}\dbinom{p}{i}F(i+1)=[p=k-1]
接下来使用二项式反演,还不会的同学请见“炫酷反演魔术”。
二项式反演得到 F(p+1)=\sum\limits_{i=1}^p(-1)^{p-i}\dbinom{p}{i}[i=k-1]=(-1)^{p-k+1}\dbinom{p}{k-1}
所以 F(p)=\sum\limits_{i=1}^p(-1)^{p-i}\dbinom{p}{i}[i=k-1]=(-1)^{p-k}\dbinom{p-1}{k-1}
那么一开始的式子就变成了:
Kth\!\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\min(T)
我们带入k=1的情况,发现1th\!\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-1}\dbinom{|T|-1}{0}min(T)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}\min(T)
正和上面的经典形式相同。
喜闻乐见的是,扩展Min-Max容斥也是在期望意义下成立的,即:
E(Kth\!\max(S))=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\min(T))
题意:每秒按固定概率出现物品,求收集到 k 个物品的期望时间。
这道题还是很有难度的,这个黑牌不亏(或者是我的dp太菜了……)
分析:我们设集合 S 为某些物品的集合,物品的权值为第一次出现时间。
那么 E(\min(S)) 就是这些物品中有其中一个出现的期望时间。
每一次得到 S 中物品的概率是 \sum\limits_{i∈S}p_i,那么期望时间就是\dfrac{1}{\sum\limits_{i∈S}p_i}。
我们能求 E(\min(S)) 了,我们再想想, E(Kth\!\min(U)) ( U 是全集)不就相当于期望耗时吗?
我们令下文的 k=n-k+1 ,求的就是 E(Kth\!\max(U)) 了,同时在题目中看到,这里的 k<=11 。
套用上面的扩展Min-Max容斥,我们就得到了式子:
{\rm Ans}=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\min(T))
但是这里的 n\leq 1000 不能直接O(2^n)统计……
我们观察发现, m<=10000 ,一道数数题居然限制值域? 没准是复杂度和 m 有关的 dp。
这个 dp 十分复杂,具体过程就不放在这里了,其余请见 题解 P4707 【重返现世】
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
总结:
Min-Max容斥,考察范围较窄,学过的基本一眼就能看出来(flag)
但是可以结合期望,集合求和dp优化或者容斥,二项式反演来考,所以难度还是挺大的。
况且近年来都喜欢出毒瘤数数题,这玩意以后可能会被出成没有这么模板的题目吧,期待ing~