Min-Max容斥 & FMT

(max(S) = sum_{Tsubseteq S} (-1) ^ {|T|+1} min(T))
(max _{k}(S)=sum_{T subseteq S}(-1)^{|T|-k} C_{|T|-1}^{k-1} min (T))

有趣的是，这些式子可以推广到期望。
主要用来解决一类(max)不好算，但(min)很好算的问题上。

(FMT:)解决子集前缀和以及超集前缀和。
暂时只学了子集和的写法...

for (int i = 0; i < n; i++)
    for (int j = (1 << i); j < (1 << n); j++)
        if (j & (1 << i)) f[j] += f[j ^ (1 << i)];

例题( ext{A}): 「HAOI2015」按位或

考虑直接硬套( ext{min-max})容斥。

对于里面的(min)，考虑把选到这些子集抽象成一个事件。
于是就有了(prob(S)=sum_{i&S!=0} p_i)，故可以算出期望次数(step(S)=1/prob(S)).
朴素复杂度(O(4 ^ n))。
考虑容斥出(prob(S))，即总可能的减掉不合法的。这个不合法的可以枚举子集，所以更优的方法是枚举补集的子集，(O(3 ^ n)).

考虑满分做法，即外面的那坨东西直接先(O(2 ^ n * n))用子集和预处理出来，每次直接查询。

	scanf ("%d", &n);
	for (int i = 0; i < (1 << n); i++) scanf ("%lf", &p[i]), f[i] = p[i];
	
	 
	for (int i = 0; i < n; i++)
		for (int j = (1 << i); j < (1 << n); j++)
			if (j & (1 << i)) f[j] += f[j ^ (1 << i)];
	
	
	double ans = 0;
	int s = (1 << n) - 1;  
	for (int t = 0; t < (1 << n); t++) {
		double dt = pow(-1, (__builtin_popcount(t) + 1));
		double prob = f[s] - f[s ^ t]; 
		if (prob) ans += dt / prob; 
	}
	
	if (ans) cout << fixed << setprecision(10) << ans << endl;
	else puts("INF");