题解 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容斥就做完了~对了，真的是超级好写！ 上代码吧~ ```C #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;\\拜拜程序~ } ```