题目

分析

按位去看，最终的答案要求 \(E(\max S)\) 就是 \(S\) 出现的期望时间。

根据min-max容斥，\(E(\max S)=\sum_{T\subset S}(-1)^{|T|-1}E(\min T)\)

那么 \(E(\min T)\) 也就是 \(T'\subset T\) 出现的期望时间，与不在 \(T\) 中的 1 不能出现的概率有关

下面这个求和可以用子集卷积实现，FWT 的或卷积就可以做到 \(O(2^nn)\)

代码

#include 
#define rr register
using namespace std;
const int N=1050011;
int n,al,xo[N]; double f[N],ans;
inline void FWT_OR(double *f){
	for (rr int p=2;p<=n;p<<=1){
		rr int len=p>>1;
		for (rr int i=0;i1e-8)
	    ans+=(xo[i]&1?1:-1)/(1-f[al^i]);
	if (ans<1e-8) printf("INF");
	    else printf("%.8lf",ans);
	return 0;
}