[HAOI2015]按位或
题目描述
刚开始你有一个数字 \(0\)，每一秒钟你会随机选择一个 \([0,2^n-1]\) 的数字，与你手上的数字进行或（C++,C 的 |，pascal 的 or）操作。选择数字 \(i\) 的概率是 \(p_i\)。保证 \(0\leq p_i \leq 1\)，\(\sum p_i=1\) 。问期望多少秒后，你手上的数字变成 \(2^n-1\)。
输入格式
第一行输入 \(n\) 表示 \(n\) 个元素，第二行输入 \(2^n\) 个数，第 \(i\) 个数表示选到 \(i-1\) 的概率。
输出格式
仅输出一个数表示答案，绝对误差或相对误差不超过 \(10^{-6}\) 即可算通过。如果无解则要输出 INF。
样例 #1
样例输入 #1
2
0.25 0.25 0.25 0.25
样例输出 #1
2.6666666667
提示
对于 \(100\%\) 的数据，\(n\leq 20\)。
Solution
设 \(\min\{S\}\) 表示 \(S\) 中第一个变为 \(1\) 的时间，\(\max\{S\}\) 表示 S 中最后一个变为 \(1\) 的时间（\(S\) 是一个二进制数）。那么有等式：
\[\begin{array}{}\displaystyle\max\{S\}=\sum\limits_{T\subseteq S} (-1)^{|T|+1}\min\{T\}\\\displaystyle\min\{S\}=\sum\limits_{T\subseteq S} (-1)^{|T|+1}\max\{T\}\end{array} \]这个等式也叫做 \(\min/\max\) 容斥，并且这个等式在期望意义下也成立：
\[\begin{array}{}\displaystyle E(\max\{S\})=\sum\limits_{T\subseteq S}(-1)^{|T|+1}E(\min\{T\})\\\displaystyle E(\min\{S\})=\sum\limits_{T\subseteq S}(-1)^{|T|+1}E(\max\{T\})\end{array} \]此题要求的显然是 \(E(\max\{S\}),S=(2^n-1)\)，并且数据范围允许枚举集合 \(T\)，那么考虑如何计算 \(E(\min\{T\})\)。有式子：
\[E(\min\{T\})=\dfrac 1 {\displaystyle\sum\limits_{G\cap T\neq \varnothing} P(G)} \]其中 \(P(G)\) 表示出现的数是 \(G\) 的概率。由于 \(G\cap T\neq \varnothing\) 并不好计算，正难则反，令 \(X=\complement_{S} T\)，即 \(X=T\oplus S\)，那么有 \(\forall G\cap T=\varnothing,G\subseteq X\)，那么不符合条件的 \(G\) 就好计算了，处理一下 \(X\) 的子集和即可，记 \(X\) 的子集和为 \(P'(X)\)，那么就有：
\[E(\min\{T\})=\dfrac 1 {1-P'(x)} \]对于 \(X\) 的子集和，显然有 \(P'(X)=\displaystyle\sum\limits_{X=Y\lor X}P(Y)\)，这个就是 FWT 的形式，直接用 FWT 处理即可。
时间复杂度 \(\mathcal O(n2^n)\)。
#include<bits/stdc++.h>
using namespace std;
constexpr int _N = (1 << 20) + 5;
constexpr double eps = 1e-8;
int n, N; double P[_N], ans;
void FWTor(double *A) {
for (int i = 1; i < N; i <<= 1)
for (int j = 0; j < N; j += i << 1)
for (int k = 0; k < i; ++k)
A[i + j + k] += A[j + k];
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n; N = 1 << n;
for (int i = 0; i < N; ++i) cin >> P[i];
FWTor(P);
for (int i = 1; i < N; ++i) if ((1 - P[(N - 1) ^ i]) > eps)
ans += ((__builtin_popcount(i) & 1) ? 1 : -1) / (1 - P[(N - 1) ^ i]);
if (ans < eps) cout << "INF" << '\n';
else cout << fixed << setprecision(10) << ans << '\n';
}