「LOJ 2127」「HAOI2015」按位或

LOJ #2127

题意

你有一个数字 $0$，每秒你会以 $p_i$ 的概率选择 $i$，$i\in[0,2^n-1]$，和自己的数进行按位或，问期望多少秒后数字变成 $2^n-1$

$n\le20,\sum p_i=1$

分析

参考2015候选队论文 吕凯风《集合幂级数的性质与应用及其快速算法》

把 $p$ 看成集合幂级数，用集合并卷积定义乘法。

设 $U={0,\dotsc,n-1}$， 那么游戏在第 $k$ 秒结束的概率是 $p^k-p^{k-1}$ 的第 $U$ 项，答案等于

$$f=\sum_{k=1}^\infty k(p^k-p^{k-1})$$

的第 $U$ 项

做莫比乌斯变换

$$
\begin{align}
\hat{f}S&=\sum{k=1}^\infty k(\hat{p}_S^k-\hat{p}S^{k-1})\
&=\sum{k=0}^\infty-\hat{p}_S^k\
&=
\begin{cases}
-\frac{1}{1-\hat{p}_S}, & \hat{p}_S\ne1\
0, & \hat{p}_S=1
\end{cases}
\end{align}
$$

再对 $\hat{f}$ 做莫比乌斯反演得到 $f$

注意特判无解

时间复杂度 $\mathcal O(n\times 2^n)$

---

这里存在

$$\sum_{i=0}^{2^n-1}f_i=0$$

还没理解

update:

$$\because\hat{p}U=\sum{S\subseteq U}p_S=1$$

$$\therefore\sum_{S\subseteq U}f_S=\hat{f}_U=0$$

---

代码

#include<cstdio>
#include<math.h>
int n;
double a[1<<20];
int main() {
	scanf("%d", &n);
	for(int i=0; i<1<<n; ++i) scanf("%lf", a+i);
	for(int i=0; i<n; ++i) for(int j=0; j<1<<n; ++j) if(j>>i&1) a[j]+=a[j^(1<<i)];
	for(int i=0; i<1<<n; ++i) a[i]=(fabs(a[i]-1)<1e-10?0:-1/(1-a[i]));
	for(int i=0; i<n; ++i) for(int j=0; j<1<<n; ++j) if(j>>i&1) a[j]-=a[j^(1<<i)];
	return a[(1<<n)-1]?printf("%.9lf", a[(1<<n)-1]):puts("INF"), 0;
}