LibreOJ 2127 「HAOI2015」按位或

发表于 | 分类于 |

嗯……要做这题首先要会一个十分有趣但其实又略带几分显然的容斥： \[ \max(S) = \sum\limits_{T \subseteq S} (-1)^{|T|+1} \min(S) \\ \min(S) = \sum\limits_{T \subseteq S} (-1)^{|T|+1} \max(S) \]

证明挺简单的，这里只证第一条。
对于排名为 \(|S|-k\) 的元素，考虑构造一个容斥系数 \(f(|T|)\) 使得 \[ [k=0] = \sum\limits_{i=0}^k \binom ki f(i+1) \]

二项式反演得 \[ \begin{aligned} f(k+1) &= \sum\limits_{i=0}^k (-1)^{k-i} \binom ki [i=0] \\ &= (-1)^k \\ f(k) &= (-1)^{k+1} \end{aligned} \]

证毕。

好玩的是这个玩意对期望也有用，所以就可以用来做这道题。
考虑把题目中给的「按位或」和「二进制数」看做集合操作，\(\min(S) / \max(S)\) 分别表示 \(S\) 集合内第一个 / 最后一个变为 \(1\) 的步数。
则我们要求的就是 \[ E(\max(U)) = \sum\limits_{T \subseteq U} (-1)^{|T|+1} E(\min(T)) \] 其中 \(U=\{i \mid 0 \le i < n\}\)。

于是现在就是要求 \(E(\min(S))\)。
考虑 \(P(\min(S)=i)\)，这意味着前 \(i\) 秒选择的集合都与 \(S\) 不相交，而第 \(i\) 秒选择的集合与 \(S\) 相交。
即 \[ P(\min(S)=i) = \left(\sum\limits_{S\cap T=\varnothing} p_T\right)^i \left(1-\sum\limits_{S\cap T=\varnothing} p_T\right) \]

设 \(w = \sum\limits_{S\cap T=\varnothing} p_T\)，则 \[ \begin{aligned} E(\min(S)) &= \sum\limits_{i=1}^{\infty} iw^{i-1}(1-w) \\ &= (1-w)\sum\limits_{i=1}^{\infty} iw^{i-1} \\ (1-w)E(\min(S)) &= (1-w)\sum\limits_{i=1}^{\infty} iw^{i-1} - (1-w)\sum\limits_{i=1}^{\infty} (i-1)w^{i-1} \\ &= (1-w)\sum\limits_{i=1}^{\infty} w^{i-1} \\ E(\min(S)) &= \sum\limits_{i=1}^{\infty} w^i \\ &= \frac1{1-w} \end{aligned} \]

那么注意到 \(w = \sum\limits_{S\cap T=\varnothing} p_T = \sum\limits_{T \subseteq \complement_U S} p_T\)，拿 FWT / FMT 求个卷积就行了。

代码： 

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
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1 << 20;
const double eps = 1e-8;
int n;
double f[N + 5],ans;
inline void fwt_or(double *a,int type)
{
    for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
        for(register int i = 0;i < n;i += w)
            for(register int j = 0;j < m;++j)
                a[i | j | m] += type * a[i | j];
}
int main()
{
    scanf("%d",&n),n = 1 << n;
    for(register int i = 0;i < n;++i)
        scanf("%lf",f + i);
    fwt_or(f,1);
    for(register int i = 1;i < n;++i)
    {
        if(1 - f[(n - 1) ^ i] < eps)
        {
            puts("INF");
            return 0;
        }
        ans += 1 / (1 - f[(n - 1) ^ i]) * (__builtin_popcount(i) & 1 ? 1 : -1);
    }
    printf("%.10f\n",ans);
}