题解 P3175 【[HAOI2015]按位或】

· · 题解

真的套路啊……，没啥好说的，这种题知道结论就秒出然后不知道结论就直接gg了

好了让我们来讲正解吧，这就是到纯数学题，没啥好说的……

我知道胡乱设一坨变量然后倒来倒去非常没人性，但是数学题就是得耐下心来推式子啊……

本题题解

前置芝士1：min-max容斥原理

所谓min-max容斥原理，其实就是两个很简单的等式

记max(S)为集合S中的最大值，min(S)为集合S中的最小值，|S|为集合S的元素数量，那么以下两个等式成立

max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}min(T)

min(S)=\sum_{T\subseteq S}(-1)^{|T|+1}max(T)

所谓的min-max容斥原理大概就是这两个简单的等式了，它真正暴力的地方在于我们就算根本没法进行大小比较，也可以仅通过加减法把max或者min以极其暴力的方式O(2^n)的枚举子集容斥出来

下面我们尝试着给出证明，这里只证明第一个等式好了，后边的可以自行推出

其实只需要证明一件事，就是除了min(T)=max(S)的那个值，其他的min值都被消掉了就可以了(这里说明一下，我们假定集合中的元素两两相异，如果存在相同的值的话，我们给其中几个加上一些eps扰动一下即可，反正不影响最值就是了)

先来说明max(S)的系数为什么是1，假设中S最大的元素是a，那么我们会发现只有min({a})=max(S)所以max(S)的系数必须是1

然后再说明为什么别的min都被消掉了，假设某个元素b的排名是k，那么min(T)=b当且仅当我们选出的集合是后n-k个的元素构成的集合的子集然后并上{b}得到的，我们会发现显然这样的集合有2^{n-k}种，而显然这其中恰有2^{n-k-1}中是有奇数个元素的，恰有2^{n-k-1}种是有偶数个元素的，两两相消自然就成0了，当然上述等式在k=n的时候不成立，但是此时剩下的刚好是最大值，所以证明完毕~

一些推导

现在我们有了非常暴力的min-max定理了，让我们来看看我们可以干一些什么事

一个令人惊讶的事实是，min-max定理在期望下成立，我们记E(max(S))为集合中max值的期望，那么有

E(max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(min(T))

E(min(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(max(T))

好了我们现在发现如果认为某个位置变为1的步数是一个随机变量的话

那么E(max(S))可以认为是某个集合S中所有位置变成1的期望步数，因为最晚的位置都变成1了，所有的位置自然都变成1了

那么很现实的一个事情是，我们没法比较两个位置变成1的期望步数长短，所以我们要使用min-max容斥原理在一无所知的(也就是说没有办法比较大小)情况下的求出max来

但是我们必须有一个求出min的方式……否则min-max容斥就是白搭，也就是说我们需要求E(min(T))换句话说，集合T中至少有一个位置变成1的最早时间

前置芝士2：离散随机变量的几何分布

先说啥叫离散随机变量

离散随机变量就是一个随机变量只可以取一些特定的不连续值，比如全体正整数之类的……

那么我们描述一个离散随机变量的最朴素的方式就是列一个表……，打出每个值的概率，然后就可以描述一个离散随机变量的分布了

那么所谓的集合分布呢，就是这里有一个离散型随机变量X,满足

P(x==k)=(1-p)^{k-1}p (k\in N^{+})

其中p是一个常量

然后我们就说这个离散型随机变量X服从带参数p的集合分布

然后不如让我来试着求一下一个服从几何分布的随机变量的期望？

E(X)=\sum_{i=1}^{+ \infty}iP(x==i)

=p\sum_{i=1}^{+ \infty} i(1-p)^{i-1}

然后我们发现这大概是一个等比数列*等差数列的数列求和的式子

运用一些基本的高中数学知识

可以算出来是这个式子

E(x)=p\frac{1}{(1-(1-p)^2}=p\frac{1}{p^2}=\frac{1}{p}

是不是很神奇？

好了有了这个我们可以做什么呢？

另一些推导

书接上回，我们现在要求E(min(T))了

那么也就是说，集合T中至少有一个位置变为1的期望步数

那么我们可以发现P(min(T)==k)的意义就是前k-1次都没有选中这个集合中的哪怕一个数，换句话来讲，前k-1次都是选了这个集合补集的子集，然后第k次没有选这个集合补集的子集，可以列出这样一个式子,我们记P(S)为选中S子集的概率之和

P(min(T)==k)=P(S\oplus T)^{k-1}(1-P(S \oplus T))

这是什么？我们发现min(T)服从系数为(1-P(S\oplus T))的几何分布！

然后期望直接套公式计算就行啦！

现在的问题是，怎么求P(T)呢？

前置芝士3:快速莫比乌斯变换(FMT)

简单来说，快速莫比乌斯变换就是快速傅里叶变换的一个兄弟……

只不过FFT的卷积是和卷积，就是i+j=k，而FMT的卷积是i|j=k也就是按位或卷积

但是和fft繁杂的变换式不一样，我们的FMT的变换式非常简单,记\hat{f}(x)为f(x)在FMT后的第x项系数，那么有

\hat{f}(x)=\sum_{T \subseteq x} f(x)

这是什么？这就是子集和！

更加令人兴奋的是，FMT可以分治，可以分治！

分治方法和FFT的分治方式几乎一样，但是唯一的不同就是不需要二进制平摊翻转置换，也不需要虚数运算，变换公式就是

a_{i}=a_{i},a_{i+k}=a_{i}+a_{i+k}

最后的推导

然后问题已经显而易见了，我们只要对原概率数组求一遍FMT即可求出P(T)了

然后就直接min-max容斥即可，如果分母为0的话直接输出inf即可了

所以这道非常套路的FMT+min-max容斥就做完了~对了，真的是超级好写！

上代码吧~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=1048580;typedef double db;db eps=1e-10;
int n;db a[N];db res;int up;int siz[N];
int main()
{
    scanf("%d",&n);up=(1<<n);
    for(int i=0;i<up;i++)scanf("%lf",&a[i]);
    for(int k=1;k<up;k<<=1)\\FMT板子
        for(int s=0;s<up;s+=k<<1)
            for(int i=s;i<s+k;i++)
            {db a0=a[i];db a1=a[i+k];a[i]=a0;a[i+k]=a0+a1;}
    for(int i=1;i<up;i++){siz[i]+=siz[i>>1]+(i&1);}
    for(int i=1;i<up;i++)\\min-max容斥
    {
        if(1-a[(up-1)^i]<eps){printf("INF\n");return 0;}
        db ex=1/(1-a[(up-1)^i]);if(siz[i]%2){res+=ex;}else {res-=ex;}
    }printf("%.10lf",res);return 0;\\拜拜程序~
}