Description
刚开始你有一个数字 \(0\) ，每一秒钟你会随机选择一个 \([0,2^n-1]\) 的数字，与你手上的数字进行或（ \(\text{or}\) ）操作。选择数字 \(i\) 的概率是 \(p_i\) 。保证 \(0\leq p_i\leq 1\) ， \(\sum_{i=0}^{2^n-1}p_i=1\) 。问期望多少秒后，你手上的数字变成 \(2^n-1\) 。
\(1\leq n\leq 20\)
Solution
不妨假设第 \(i\) 秒后状态为 \(S\) 的概率为 \(fp_{i,S}\)
显然 \(i=1\) 时， \(fp_{1,S}=p_S\) 。
注意到 \(fp\) 会满足这样的关系
\[fp_{i,S} = \sum_{L \subseteq S} \sum_{R \subseteq S}^{} [L \cup R = S] fp_{i-1,L} \times p_R\]
记 \(U=2^n-1\) ，于是我们可以得到答案就是
\[\sum_{i=1}^\infty i(fp_{i,U}-fp_{i-1,U})\]
其中 \(fp_{i,U}-fp_{i-1,U}\) 表示恰好第 \(i\) 时变为 \(U\) 的概率。
记 \(FP\) 为 \(fp\) 的莫比乌斯变换，记 \(P\) 为 \(p\) 的莫比乌斯变换。显然 \(FP_{i,S}=P_S^i\) 。
那么对于集合 \(S\) 在莫比乌斯变换下得到的答案就是
\[\begin{aligned}&\sum_{i=1}^\infty i(P_S^i-P_S^{i-1})\\=&\begin{cases}-(P_S^0 +P_S^1+\cdots+P_S^\infty)&P_S<1\\0&P_S=1\end{cases}\\=&\begin{cases}-\frac{1}{1-P_S}&P_S<1\\0&P_S=1\end{cases}\end{aligned}\]
然后再反演回去直接得到答案即可。复杂度 \(O(n2^n)\) 。
Code
#includeusing namespace std;const int N = 25, SIZE = (1<<20)+5;const double eps = 1e-7;int bin[N], n;double p[SIZE];void FMT(double *f, int o) { for (int i = 1; i < bin[n]; i <<= 1) for (int j = 0; j < bin[n]; j++) if (i&j) f[j] += f[j^i]*o;}void work() { scanf("%d", &n); bin[0] = 1; for (int i = 1; i <= n; i++) bin[i] = (bin[i-1]<<1); for (int i = 0; i < bin[n]; i++) scanf("%lf", &p[i]); FMT(p, 1); for (int i = 0; i < bin[n]; i++) if (fabs(p[i]-1) <= eps) p[i] = 0; else p[i] = 1./(p[i]-1.); FMT(p, -1); p[bin[n]-1] <= eps ? puts("INF") : printf("%.7lf\n", p[bin[n]-1]);}int main() {work(); return 0; }