LibreOJ 2127.「HAOI2015」按位或

嗯……要做这题首先要会一个十分有趣但其实又略带几分显然的容斥: \[ \max(S) = \sum\limits_{T \subseteq S} (-1)^{|T|+1} \min(S) \\ \min(S) = \sum\limits_{T \subseteq S} (-1)^{|T|+1} \max(S) \]

证明挺简单的,这里只证第一条。
对于排名为 \(|S|-k\) 的元素,考虑构造一个容斥系数 \(f(|T|)\) 使得 \[ [k=0] = \sum\limits_{i=0}^k \binom ki f(i+1) \]

二项式反演得 \[ \begin{aligned} f(k+1) &= \sum\limits_{i=0}^k (-1)^{k-i} \binom ki [i=0] \\ &= (-1)^k \\ f(k) &= (-1)^{k+1} \end{aligned} \]

证毕。

好玩的是这个玩意对期望也有用,所以就可以用来做这道题。
考虑把题目中给的「按位或」和「二进制数」看做集合操作,\(\min(S) / \max(S)\) 分别表示 \(S\) 集合内第一个 / 最后一个变为 \(1\) 的步数。
则我们要求的就是 \[ E(\max(U)) = \sum\limits_{T \subseteq U} (-1)^{|T|+1} E(\min(T)) \] 其中 \(U=\{i \mid 0 \le i < n\}\)

于是现在就是要求 \(E(\min(S))\)
考虑 \(P(\min(S)=i)\),这意味着前 \(i\) 秒选择的集合都与 \(S\) 不相交,而第 \(i\) 秒选择的集合与 \(S\) 相交。
\[ P(\min(S)=i) = \left(\sum\limits_{S\cap T=\varnothing} p_T\right)^i \left(1-\sum\limits_{S\cap T=\varnothing} p_T\right) \]

\(w = \sum\limits_{S\cap T=\varnothing} p_T\),则 \[ \begin{aligned} E(\min(S)) &= \sum\limits_{i=1}^{\infty} iw^{i-1}(1-w) \\ &= (1-w)\sum\limits_{i=1}^{\infty} iw^{i-1} \\ (1-w)E(\min(S)) &= (1-w)\sum\limits_{i=1}^{\infty} iw^{i-1} - (1-w)\sum\limits_{i=1}^{\infty} (i-1)w^{i-1} \\ &= (1-w)\sum\limits_{i=1}^{\infty} w^{i-1} \\ E(\min(S)) &= \sum\limits_{i=1}^{\infty} w^i \\ &= \frac1{1-w} \end{aligned} \]

那么注意到 \(w = \sum\limits_{S\cap T=\varnothing} p_T = \sum\limits_{T \subseteq \complement_U S} p_T\),拿 FWT / FMT 求个卷积就行了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1 << 20;
const double eps = 1e-8;
int n;
double f[N + 5],ans;
inline void fwt_or(double *a,int type)
{
for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
for(register int i = 0;i < n;i += w)
for(register int j = 0;j < m;++j)
a[i | j | m] += type * a[i | j];
}
int main()
{
scanf("%d",&n),n = 1 << n;
for(register int i = 0;i < n;++i)
scanf("%lf",f + i);
fwt_or(f,1);
for(register int i = 1;i < n;++i)
{
if(1 - f[(n - 1) ^ i] < eps)
{
puts("INF");
return 0;
}
ans += 1 / (1 - f[(n - 1) ^ i]) * (__builtin_popcount(i) & 1 ? 1 : -1);
}
printf("%.10f\n",ans);
}