P3175 [HAOI2015]按位或
设\(A_i\)表示第\(i\)位变为\(1\)的时间，那么答案就是\(max(A)\)。发现\(max(A)\)不好直接求，但\(min(A)\)很好求，考虑\(min-max\)容斥。
那么 \(E(max(A)) = \sum_{T \subseteq A}(-1)^{|T| + 1}E(min(T))\)
其中 \(E(min(T)) = \sum_{k \ge 1} k * P(min(T))_k\)，其中 \(P(min(T))_k\)表示第\(k\)秒，选中了\(T\)中的数。
那么 \(P(min(T))_k = f(T \oplus U)^{k-1} * (1 - f(T \oplus U))\)，其中\(U\)为全集，\(f(X) = \sum_{x \subseteq X}p_x\)，\(p_x\)为选\(x\)的概率。
带入得\(E(min(T)) = \frac{1}{1 - f(T \oplus U)}\)。
那么\(f\)用\(FWT\)求即可。
Code
#include<cstdio>
using namespace std;
const int N = 1 << 21;
int n, siz[N]; double p[N], f[N];
int main()
{
scanf("%d",&n);
for (int i = 0; i < (1 << n); i++) scanf("%lf", &p[i]);
for (int i = 0; i < n; i++)
for (int j = 0; j < (1 << n); j++)
if (j & (1 << i)) p[j] += p[j ^ (1 << i)];
for (int i = 0; i < (1 << n); i++) f[i] = 1.0 / (1.0 - p[i ^ ((1 << n) - 1)]);
double ans = 0;
for (int i = 1; i < (1 << n); i++) {
if (1 - p[i ^ ((1 << n) - 1)] < 1e-10){puts("INF"); return 0;}
siz[i] = siz[i >> 1] + (i & 1), ans += (siz[i] & 1 ? 1.0 : -1.0) * f[i];
}
printf("%.9lf\n", ans);
}