LibreOJ 2127 「HAOI2015」按位或

嗯……要做这题首先要会一个十分有趣但其实又略带几分显然的容斥： max(S)=∑T⊆S(−1)|T|+1min(S)min(S)=∑T⊆S(−1)|T|+1max(S)

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

二项式反演得 f(k+1)=k∑i=0(−1)k−i(ki)[i=0]=(−1)kf(k)=(−1)k+1

证毕。

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

其中 U={i∣0≤i<n}。

于是现在就是要求 E(min(S))。
考虑 P(min(S)=i)，这意味着前 i 秒选择的集合都与 S 不相交，而第 i 秒选择的集合与 S 相交。
即 P(min(S)=i)=(∑S∩T=∅pT)i(1−∑S∩T=∅pT)

设 w=∑S∩T=∅pT，则 E(min(S))=∞∑i=1iwi−1(1−w)=(1−w)∞∑i=1iwi−1(1−w)E(min(S))=(1−w)∞∑i=1iwi−1−(1−w)∞∑i=1(i−1)wi−1=(1−w)∞∑i=1wi−1E(min(S))=∞∑i=1wi=11−w

那么注意到 w=∑S∩T=∅pT=∑T⊆∁USpT，拿 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);
}