LuoguP3175「HAOI2015」题解

发表于 更新于

Min-Max容斥 + 数学技巧 + 位运算卷积优化

题目描述

刚开始你有一个数字0，每一秒钟你会随机选择一个[0,2^n-1]的数字，与你手上的数字进行或（c++,c的|,pascal的or）操作。

选择数字i的概率是p[i]。保证0<=p[i]<=1，Σp[i]=1问期望多少秒后，你手上的数字变成2^n-1。

输入格式

第一行输入n表示n个元素，第二行输入2^n个数，第i个数表示选到i-1的概率

输出格式

仅输出一个数表示答案，绝对误差或相对误差不超过1e-6即可算通过。如果无解则要输出INF

Inputs and Outputs examples

Inputs’ e.g. #1

1
2
2
0.25 0.25 0.25 0.25

Outputs’ e.g. #1

1
2.6666666667

数据范围

对于100%的数据，n<=20

分析

先扯几句没啥关系的事.

没错,这个写题解的菜鸡就是某假人博客上那个00:00装13切黑题然后赖床到八点的女孩子

ezFISg.png

不扯了………

我们发现或运算在进行的时候对于一个数的每一位都是独立的.

那么我们分开来考虑每一位.

我们设$a_i$表示第$i$位变成$1$的时间.

那么我们要求的是$E(\max({\rm U})) \quad{\rm U}\text{为解的全集}$.

根据Min-Max容斥,我们只要求出$E(\min({\rm U}))$就能算出答案了,那么考虑设$P(S)$表示选中集合$S$的概率,$P’(S)$表示选中$S$的子集的概率.

设事件$A = [\min(S) = k]$,那么

$$P(A) = P’(\complement_US) ^ {k-1} (1 - P’(\complement_US))$$

这个式子是说,$P(A)$就是:我们前$k-1$选取了$S$的补集的子集,最后一次不能选$S$的补集的子集的概率之积

那么考虑枚举$k$,就可以得到:

$$E(\min(S)) = \sum_{k=1}^\infty kP(A) = \sum_{k=1}^\infty k \times P’(\complement_US) ^ {k-1} (1 - P’(\complement_US))$$

设$p = P’(\complement_US)$,那么原式:

$$(1 - p)\sum_{k=1}^\infty k \cdot p^{k-1}$$

我们发现后面的式子显然是个等差*等比数列求和形式,考虑错位相减法.

设数列$T = \left( 1 \times 1, 2 \times p, 3 \times p^2, 4 \times p^3 \dots k \times p^{k-1} \dots \right)$

那么${\rm Sum}_T = 1 \times 1 + 2 \times p + 3 \times p^2 + 4 \times p^3 + \dots + k \times p^{k-1} \dots $

等式两边乘一个$p$,那么:

$$p \times {\rm Sum}_T = 1 \times p + 2 \times p^2 + 3 \times p^3 + 4 \times p^4 + \dots + k \times p^{k} \dots$$

两式相减可得:

$$(1 - p){\rm Sum_T} = \lim_{n \to \infty} \frac{1-p^n}{1-p} = \frac {1}{1-p}$$

$$E(\min(S)) = \frac {1}{1 - P’(\complement_US)}$$

我们的目的是求出所有的$E(\min(S))$,那么考虑求出所有的$P’(S)$.

根据初中概率知识,有:

$$P’(S) = \sum_{W \subseteq S} P(W)$$

即枚举子集,这时直接FWT位运算卷积优化即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 1e6 + 1e5 + 10;
int n,Size[MAXN];
double a[MAXN];
/* functions */
int main(int argc,char *argv[]){
    scanf("%d",&n); n = (1 << n);
    FOR(i,0,n-1,1) scanf("%lf",&a[i]);
    for(int len = 1; len < n; len <<= 1){
        for(int p = 0; p < n; p += (len << 1)){
            for(int i = p; i < p + len; i++)
                a[i+len] += a[i];
        }
    }
    double ans = 0;
    FOR(i,1,n-1,1){
        Size[i] = Size[i >> 1] + (i & 1);
        double save = (1 - a[i ^ (n - 1)]);
        if(save < 1e-8)  {puts("INF"); return 0;}
        save = 1 / save;
        ans += (Size[i] & 1) ? -save : save;
    }printf("%.10lf",-ans);
    return 0;
}

THE END