套路题
看到\(n \leq 20\)，又看到我们求的是最后出现的位置出现的时间的期望，也就是集合中最大值的期望，考虑min-max容斥。
由\(E(max(S)) = \sum\limits_{T \subset S} (-1)^{|T| + 1} E(min(T))\)，我们要求的就是一个集合至少有一个数字出现的期望时间。那么\(E(min(T)) = \frac{1}{\sum\limits_{S' \cap T \neq \emptyset} p_{S'}}\)。
\(\sum\limits_{S' \cap T \neq \emptyset} p_{S'}\)不是很好求，考虑反过来求。它等于\(1 – \sum\limits_{S' \cap T = \emptyset} p_{S'} = 1 – \sum\limits_{S' \subset (2^N – 1 – T)}p_{S'}\)，而$ \sum\limits_{S’ \subset (2^N – 1 – T)}p_{S’}$就是子集和，高维前缀和求解即可。
#include<bits/stdc++.h>#define ld long double//This code is written by Itstusing namespace std;inline int read(){ int a = 0; char c = getchar(); bool f = 0; while(!isdigit(c) && c != EOF){ if(c == '-') f = 1; c = getchar(); } if(c == EOF) exit(0); while(isdigit(c)){ a = a * 10 + c - 48; c = getchar(); } return f ? -a : a;}long double p[1 << 20];int N , cnt1[1 << 20];int main(){#ifndef ONLINE_JUDGE freopen("in","r",stdin); freopen("out","w",stdout);#endif cin >> N; int all = 0; for(int i = 0 ; i < 1 << N ; ++i){ cin >> p[i]; cnt1[i] = cnt1[i >> 1] + (i & 1); if(p[i] > 1e-6) all |= i; } if(all != (1 << N) - 1){ puts("INF"); return 0; } for(int i = 0 ; i < N ; ++i) for(int j = 0 ; j < 1 << N ; ++j) if(!(j & (1 << i))) p[j | (1 << i)] += p[j]; ld sum = 0; for(int i = 0 ; i < 1 << N ; ++i) if(1 - p[((1 << N) - 1) ^ i] > 1e-7) sum = sum + (cnt1[i] & 1 ? 1 : -1) / (1 - p[((1 << N) - 1) ^ i]); cout << fixed << setprecision(6) << sum; return 0;}
