题解 P3175 【[HAOI2015]按位或】

可能算是通过这道题学会了 Min-Max 容斥... 并且发现 FWT 并不全是个没用的东西... 这里有两个前置芝士： # 一、Min-Max 容斥 上个结论： $$Min\{S\}=\sum_{T\subseteq S,T\not=\varnothing}(-1)^{|T|-1}Max\{T\} $$ $$Max\{S\}=\sum_{T\subseteq S,T\not=\varnothing}(-1)^{|T|-1}Min\{T\} $$ 具体的证明其实很简单...我们考虑证明其中一个（以第一个为例），另一个可以用类似证法得到结论。咱直接考虑集合内元素不重的情况，因为相同大小我们强制规定他们之间存在大小关系就好了，并不影响结果 那么我们再把元素从小到大排个序，从前往后考虑每个值对答案的贡献... >首先第一个元素有贡献当且仅当集合里只有它一个元素，那么这样的集合只有一个，所以它的贡献有且仅有一次； >对于第二个元素，它除了自己一定要选以外，比他小的元素（这时只有第一个元素）全部可选可不选，总共有 $2^{1}=2$ 种方案，并且集合大小为奇数和为偶数的情况各有一次，两者贡献抵消 >对于后面的元素，可以用第二个元素类似的思路去想，最后我们发现除第一个元素以外的所有贡献都相互抵消了 当然咱也可以用二项式定理草率地证明一下，然后也能发现贡献相抵了，究其原因就是杨辉三角奇数列和偶数列之差为 0 ，而第一行为 1 是个特例 （因为只有一个元素） 于是乎得证... 但更重要的一点，我们发现这道题的期望步数满足可 Min-Max 容斥的性质： $$E(Max\{S\})=\sum_{T\subseteq S,T\not=\varnothing}(-1)^{|T|-1} E(Min\{T\}) $$ 这里的 $E(Max\{S\})$ 表示集合 S 中出现最晚的元素出现的期望步数，而 $E(Min\{S\})$ 则是集合 S 中出现最早的元素出现的期望步数 那么我们可以发现其实 $E(Max\{2^n-1\})$ 就是要求的答案... # 二、FWT 的第一步 之所以说第一步...是因为这道题真的就只要用到 FWT 的第一步（子集和计算） FWT 本身是求两个多项式的位运算卷积（简直毒瘤），其中或运算的 FWT 第一步就要用到子集和计算，对此咱可以用一段和 法法塔 极其相似的代码求解... 具体关于 FWT 的运算可以康康 [yyb聚聚](https://www.cnblogs.com/cjyyb/p/9065615.html) 和 [wjyyy聚聚](https://www.cnblogs.com/wjyyy/p/FWT.html) 写的博客... 为什么要用 FWT 相关知识？因为枚举子集 $3^n$ 复杂度爆炸了 或者康康 [这里](https://www.cnblogs.com/Judge/p/10920451.html) 的第三条... 如果令 $n$ 为多项式长度，其实 FWT 的复杂度是 $n ~log~ n$ ，而这道题长度为$2^n$ 所以复杂度为 $n·2^n $ 但为什么要用到计算子集和呢？ 【冷静分析... 因为咱要求 $E(Min\{S\})$ 哇... 这玩意儿就表示 S 集合最早出现的元素期望的步数，那么这个值就等于所有和 S 交集不为空的值最早出现的期望步数，公式化表示一下就是： $$E(Min\{S\})={1\over \sum_{T\cap S\not=\varnothing} P(T)}$$ 这里 $P(T)$ 表示的是 T 这个值出现的概率，那么期望等于 1 除去概率这一点...您感性理解一下好了...这里由于所有满足条件的 T 只要出现一个即可，那么他们出现的概率之和 分之一 就是 S 中有元素出现的期望步数 ... 那么咱发现这玩意儿贼难求...和 S 有交集？ wdnmd 这怎么求啊...但是咱发现所有的值 $[0,2^n-1]$ 出现的概率之和是 $1$ ，那么咱可以用 1 容去不满足条件的 T 出现概率之和，然后咱得到的其实就是要求的东西啊... 随后咱发现不满足条件的 T 就是总集中 S 的补集的所有子集...emmmm 有点绕，但并不影响解题...咱令 S 的补集为 S' ，那么咱原来要求的东西就变成了： $$E(Min\{S\}) ={1\over 1-\sum_{T\subseteq S'} P(T)}$$ 这样咱只要求出所有的 $S'$ 的子集概率和即可 $O(1)$ 得到 $E(Min\{S\})$ ，然后咱就可以 $O(2^n)$ 用 Min-Max 容斥得到答案辣~ # code 证明也证明完了，那么咱处理个子集和然后就可以计算答案了... 发现代码特别短...【话说咱一发上了 $top~4$ 是个什么鬼 ... ``` //by Judge #include<bits/stdc++.h> #define Rg register #define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i) int n,cnt[1<<20],N; double p[1<<20],ans; int main(){ cin>>n,N=1<<n; fp(i,0,N-1) cin>>p[i],cnt[i]=cnt[i>>1]+(i&1); for(Rg int i=1;i<N;i<<=1) for(int I=i<<1,j=0;j<N;j+=I) fp(k,0,i-1) p[i+j+k]+=p[j+k]; fp(i,1,N-1) if(1-p[(N-1)^i]>1e-8) ans+=((cnt[i]&1)?1:-1)/(1-p[(N-1)^i]); if(ans<1e-10) return !printf("INF\n"); else printf("%.10lf\n",ans); } ```