LibreOJ 2127 「HAOI2015」按位或

嗯……要做这题首先要会一个十分有趣但其实又略带几分显然的容斥：

$$\begin{gathered} max(S)=\sum _{T\subseteq S}(-1{)}^{|T|+1}min(S) \\ min(S)=\sum _{T\subseteq S}(-1{)}^{|T|+1}max(S) \end{gathered}$$

证明挺简单的，这里只证第一条。
对于排名为 $|S|-k$ 的元素，考虑构造一个容斥系数 $f(|T|)$ 使得

$$[k=0]=\sum _{i=0}^k(\genfrac{}{}{0ex}{}{k}{i})f(i+1)$$

二项式反演得

$$\begin{array}{rl}f(k+1)& =\sum _{i=0}^k(-1{)}^{k-i}(\genfrac{}{}{0ex}{}{k}{i})[i=0]\\ & =(-1{)}^k\\ f(k)& =(-1{)}^{k+1}\end{array}$$

证毕。

好玩的是这个玩意对期望也有用，所以就可以用来做这道题。
考虑把题目中给的「按位或」和「二进制数」看做集合操作，$min(S)/max(S)$ 分别表示 $S$ 集合内第一个 / 最后一个变为 $1$ 的步数。
则我们要求的就是

$$E(max(U))=\sum _{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 _{S\cap T=\varnothing }{p}_T\right)}^i\left(1-\sum _{S\cap T=\varnothing }{p}_T\right)$$

设 $w=\sum _{S\cap T=\varnothing }{p}_T$，则

$$\begin{array}{rl}E(min(S))& =\sum _{i=1}^{\mathrm{\infty }}i{w}^{i-1}(1-w)\\ & =(1-w)\sum _{i=1}^{\mathrm{\infty }}i{w}^{i-1}\\ (1-w)E(min(S))& =(1-w)\sum _{i=1}^{\mathrm{\infty }}i{w}^{i-1}-(1-w)\sum _{i=1}^{\mathrm{\infty }}(i-1)w^{i-1}\\ & =(1-w)\sum _{i=1}^{\mathrm{\infty }}{w}^{i-1}\\ E(min(S))& =\sum _{i=1}^{\mathrm{\infty }}{w}^i\\ & =\frac{1}{1-w}\end{array}$$

那么注意到 $w=\sum _{S\cap T=\varnothing }{p}_T=\sum _{T\subseteq {\complement }_{U}S}{p}_T$，拿 FWT / FMT 求个卷积就行了。

代码：

#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);
}