min_max容斥

用途

对于一个集合S，给出每个元素出现的概率，我们需要求每一个元素都出现至少一次的期望次数,可以使用min_max容斥。

例题

HDU-4336 Card Collector

这题当然可以状压dp，注意可能随机到本身有的元素的情况即可。时间复杂度\(O(2^n*n)\)，空间复杂度\(O(2^n)\)
但是，用以下方法时空效率都会更高，时间复杂度\(O(2^n)\)，空间复杂度是\(O(n)\)的，并且非常好写。

定义

对于一个集合S
\(min(S)\)表示这个集合第一个出现的元素。
\(max(S)\)表示这个集合最后一个出现的元素。
\(P_i\)表示\(i\)号元素出现的概率，\(E\)则表示期望次数。
显然\(P(min(S))=\sum_{i\in S} P_i\),
而\(E(min(S))=\frac{1}{P(min(S))}\)(这个很显然，也比较好证明)
然后有一个结论:\(E(max(S))=\sum_{S‘\subseteq S} E(min(S‘))*(-1)^{|S‘|+1}\)(蒟蒻不会证明，不过知道结论就够了)
而对于这个问题我们要求的就是\(E(max(S))\),所以暴力搞一下就好。
时间复杂度\(O(2^n)\),但空间为\(O(20)???\)

完整代码

#include<bits/stdc++.h>
using namespace std;
const int N=21;
double a[N],ans;
int n;
void dfs(int x,double p,int k){
    if(x>n){if(p>=0.000000001)ans+=(double)k/p;return;}//注意特判P为0的情况
    dfs(x+1,p,k);
    dfs(x+1,p+a[x],-k);
}
int main(){
    while(scanf("%d",&n)!=EOF){
        ans=0;
        for(int i=1;i<=n;++i)scanf("%lf",&a[i]);
        dfs(1,0,-1);
        printf("%.10lf\n",ans);
    }
    return 0;
}