Min-Max反演学习笔记

\max\limits_{a \in A}a = \sum\limits_{S \subset A, S \neq \emptyset}(-1)^{\mid S \mid + 1}\min\limits_{a \in S}a

\min\limits_{a \in A}a = \sum\limits_{S \subset A, S \neq \emptyset}(-1)^{\mid S \mid + 1}\max\limits_{a \in S}a

证明(以第一条为例):

\max(a, b) = a + b - \min(a, b)

\max\limits_{a \in A \cup \{x\}}a = \max\limits_{a \in A}a + x - \min(\max\limits_{a \in A}a, x)

对集合大小进行归纳就行了。

Min-Max反演直接应用并不常见,但由于期望的线性性,一些最大值期望比较难求的场合可以使用Min-Max反演转化为求相对好求的最小值的期望。

例题 [BZOJ 4036] 按位或

题目要求元素0n - 1被选中时间最大值的期望,使用Min-Max反演转化为求子集中至少有一个元素被选中的时间的期望。也就是说,要求一步内选中了子集中至少一个元素的概率pp不方便直接求,进行补集转化,1 - p就是选中的子集落在给定子集的补集中的概率。问题就转化成了对每个集合求它的子集的权值之和,直接FWT就行了。

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 21;
const double EPS = 1e-9;

int n, pc[1 << MAX_N];
double p[1 << MAX_N], ans;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < 1 << n; i++) scanf("%lf", &p[i]);
    for (int i = 0; i < 1 << n; i++) pc[i] = pc[i >> 1] + (i & 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 1 << n; j++)
            if (j >> i & 1) p[j] += p[j ^ 1 << i];
    for (int i = 0; i < (1 << n) - 1; i++)
        if (p[i] > 1 - EPS)
        {
            printf("INF\n");
            return 0;
        }
    for (int i = 1; i < 1 << n; i++)
        ans += 1 / (1 - p[(1 << n) - 1 - i]) * (pc[i] & 1 ? 1 : -1);
    printf("%.9lf\n", ans);
}


发表评论

电子邮件地址不会被公开。 必填项已用*标注