min-max容斥(包含kth)

用途

对于一个集合S，给出每个元素出现的概率，我们需要求每一个元素都出现至少一次的期望次数,可以使用min-max容斥，也可以求任意\(k\)个元素出现的期望(kth min-max容斥)。

例题

这题当然可以状压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)???\)

ps:这道题每个元素之间相互独立，如果元素之间不独立但能求出每个子集的\(E(min(S'))\),也就是至少出现一个元素的期望次数，也能用min-max容斥,例如[,把每一个二进制位看做一个元素，他们本来不相互独立，但我们可以用FWT求出每个集合的min之后套公式求全集的max

完整代码

#include
    
     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>=1e-9)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;}
    

kth min-max容斥

上述公式只能求最大元素出现的期望步数

min-max还可以用来求第\(k\)大元素(也就是至少出现\(n-k+1\)个元素)出现的期望步数。

先说结论:\(kthmax(S)=\sum_{T\subseteq S}(-1)^{|T|-k}C_{|T|-1}^{k-1}min(T)\)

可以发现上面的公式就是这个公式的特殊情况，把\(k=1\)带入即可。

证明先咕一段时间，以后再补，然而用它做题也不需要证明

给个例题

 

本题将公式套上可得

\(ans=\sum_{T\subseteq S}(-1)^{|T|-k}C_{|T|-1}^{k-1}\frac{m}{sum(T)}\)

其中\(sum(T)=\sum_{i\in T}p_i\)

设\(f[i][j][x]\)表示前\(i\)个数选了\(sum(T)\)为\(j\),且将\(k=x\)带入之后前面那一串系数的和。

利用组合数优秀的性质进行转移。

\(C_n^m=C_n^{n-m}\)

\(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\)