SI's space

SI's space

人菜就要多写题

题解 P3175 【[HAOI2015]按位或】

posted on 2018-04-28 22:06:50 | under 题解 |

真的套路啊……,没啥好说的,这种题知道结论就秒出然后不知道结论就直接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;\\拜拜程序~
}