LOJ#2127. 「HAOI2015」按位或

min-max 容斥入门题。

相当于求每个位置的期望次数的最大值，用 min-max 容斥得到：

$$E(\max_{i\in S}{t_i})=\sum_{T\subseteq S}(-1)^{|T-1|} E(\min_{i\in T}t_i)$$

考虑如何求 $\displaystyle E(\min_{i\in S}t_i)$，考虑期望的离散计算方式，设 $f(S)$ 表示选中不覆盖 $S$ 中任意位置的概率，有 $\displaystyle E(\min_{i\in S} t_i)=(1-f(S))\cdot\sum_{k=1}k\cdot f(S)^{k-1}$。后面一部分推一下：

$$\begin{align} f(S) \cdot\sum_{k=1}k\cdot f(S)^{k-1} &= \sum_{k=2}(k-1)\cdot f(S)^{k-1}\notag\\ &=\sum_{k=1}k\cdot f(S)^{k-1}-\sum_{k=0}f(S)^k\\ \sum_{k=1}k\cdot f(S)^{k-1} &= \frac{\sum_{k=0}f(S)^k}{1-f(S)}\notag\\ \end{align}$$

于是得到：

$$E(\min_{i\in S} t_i)=\sum_{k=0}f(S)^k=\frac{1}{1-f(S)}$$

但其实上面推的式子是完全没有必要的，补集转换就可以得到上式。

对于 $f(S)$ 可以用 FMT 求出，总时间复杂度为 $\mathcal O(n2^n)$。

Code

#include<iostream>
#include<cstdio>
#define popcnt __builtin_popcount
using namespace std;
const int N=21,M=1<<N;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,tot;
int sum;
double ans,f[M];
inline void FMT()
{
    for(int i=0;i<n;i++)
        for(int j=0;j<tot;j++)
            if(j>>i&1)
                f[j]+=f[j^(1<<i)];
}
int main()
{
    read(n);tot=1<<n;
    for(int i=0;i<tot;i++)scanf("%lf",&f[i]),sum|=(f[i]!=0)?i:0;
    if(sum!=tot-1)return puts("INF"),0;
    FMT();
    for(int i=1;i<tot;i++)ans+=(popcnt(i)&1?1:-1)*(1.0/(1-f[tot-1^i]));
    printf("%.10lf",ans);
    return 0;
}