[HAOI2015] 按位或 题解

min_max 容斥

Statement

一个数字,从 \(0\) 开始,每次按位或上一个数 \(?? ∈ [0,2^?? ? 1]\) ,其中 \(??\) 出现的概率是 \(??_??\)

求期望多少次后该数变为 \(2^?? ? 1\)

\(?? ≤ 20,0 ≤ ??_?? ≤ 1,\sum??_?? = 1\)

Solution

前置题目

它的一道前置题目叫做： HDU4336 Card Collector

每包零食里有一张卡牌，总共有 \(N\) 种不同的卡牌，得到这 \(N\) 种卡牌的概率分别为 $ P_i(1 <= i <= N)$

求收集到所有卡牌的期望是多少。

我们不妨先看看这道题怎么做

如果题目保证了 \(\sum p_i=1\) ，那么答案应该是 \(\max(n,\dfrac 1{\max_{i=1}^n p_i})\) （我口胡的）

这里涉及到一个前置知识叫做 几何分布

几何分布

\(P (??)\) 表示进行成功率为 \(??\) 的独立实验,前 \(?? ? 1\) 次失败,第 \(??\) 次成功的概率

那么有 \(P (??) = ?? (1 ? ??)^{ ???1}\) ,\(E (??) = \frac1 ??\)

所以抽到卡牌 \(i\) 的期望次数是 \(\frac 1p\) ，而保证了 \(\sum p_i=1\) ，所以在抽不到 \(i\) 的时候必然抽到了其他的卡牌，所以如果 \(i\) 都期望抽到了，那么其他期望比 \(i\) 小的也能抽到。（纯粹口胡

所以题目没有保证 \(\sum p_i=1\) ，但是我们知道了如果至少抽到 \(i\) 这张卡牌的期望是 \(\frac 1{p_i}\)

也就是说 \(min\) 很好求而 \(max\) 不好求，所以我们考虑 \(min-max\) 容斥，定义 \(s\) 为卡片集合

那么 \(??(\max(??))\) 为 \(??\) 中所有卡片都收集到的期望, \(??(\min(??))\) 为 \(??\) 中至少收集到 \(1\) 张卡片的期望

容易知道： \(E(\min(s))=\dfrac 1{\sum _{i\in s}p_i}\) ，套用公式：

解决了这个问题。

#include
#define eps 1e-8
using namespace std;
const int N = 25;

double a[N],ans;
int n;

void dfs(int x,int cnt,double sum){
    if(x==n+1){
        if(sum>n){
        for(int i=1;i<=n;++i)cin>>a[i];
        ans=0,dfs(1,0,0);
        printf("%.8lf\n",ans);
    }
    return 0;
}

原问题

现在我们看到原问题，自然而然开始考虑同样的 \(min-max\) 容斥，考虑 \(E(\min(s))\) 的求法

记 \(f(s)\) 表示选中 \(s\) 某一个子集的概率，有：\(P(min(s)=k)=f(\complement_Us)^{k-1}(1-f(\complement_Us))\)

即 \(\min(s) = ??\) 意味着前 \(?? ? 1\) 次全部选到了 \(??\) 的补集 \(???\)当中,第 \(??\) 次选到了 \(s\) 当中的元素

之所以是 \(1 ? ?? (???)\) 而不是 \(??(??)\) 是因为并不一定要全部选到 \(??\) 当中,一部分在 \(??\) 内而一部分在 \(??\) 外仍是合法情况,即只 要不全在 \(???\) 中即可

容易发现 \(E(\min(s))=\dfrac 1{1-f(\complement s)}\)

考虑 \(f(\complement s)\) 的求法，容易发现 \(f(\complement s)=\sum_{T\subseteq s}p_t\) ，显然一个 FWT 就好。

Code

#include
#define eps 1e-7
using namespace std;
const int N = 1<<23;

double a[N],ans;
int n;

signed main(){
    scanf("%d",&n);
    for(int i=0;i<(1<>1;j<=(1<