「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;
}