[HAOI2015] 按位或

0
15011418730 LV 7 @ 2025-8-24 21:46:08
自动搬运

查看原文

来自洛谷，原作者为

shadowice1984
これが勘違いでも、これが勘違いでも

搬运于2025-08-24 21:46:08，当前版本为作者最后更新于2018-04-28 22:06:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

ID

2248

时间

1000ms

内存

125MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

本题题解

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

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

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

一些推导

$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))$

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

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

$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}$

另一些推导

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

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

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

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

最后的推导

信息

1 条题解

自动搬运

以下是正文

本题题解

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

max(S)=∑T⊆S(−1)∣T∣+1min(T)max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}min(T)max(S)=∑T⊆S​(−1)∣T∣+1min(T)

min(S)=∑T⊆S(−1)∣T∣+1max(T)min(S)=\sum_{T\subseteq S}(-1)^{|T|+1}max(T)min(S)=∑T⊆S​(−1)∣T∣+1max(T)

一些推导

E(max(S))=∑T⊆S(−1)∣T∣+1E(min(T))E(max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(min(T))E(max(S))=∑T⊆S​(−1)∣T∣+1E(min(T))

E(min(S))=∑T⊆S(−1)∣T∣+1E(max(T))E(min(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(max(T))E(min(S))=∑T⊆S​(−1)∣T∣+1E(max(T))

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

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

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

=p∑i=1+∞i(1−p)i−1=p\sum_{i=1}^{+ \infty} i(1-p)^{i-1}=p∑i=1+∞​i(1−p)i−1

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

另一些推导

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

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

f^(x)=∑T⊆xf(x)\hat{f}(x)=\sum_{T \subseteq x} f(x)f^​(x)=∑T⊆x​f(x)

ai=ai,ai+k=ai+ai+ka_{i}=a_{i},a_{i+k}=a_{i}+a_{i+k}ai​=ai​,ai+k​=ai​+ai+k​

最后的推导

[HAOI2015] 按位或

信息

还没有账户？

登录

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

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

$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))$

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

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

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

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

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

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