ABC242Ex Random Painting

AtCoder: Ex - Random Painting

需要计算所有点都被覆盖的期望，即所有点期望的最大值。考虑 Min-Max 反演，计算所有子集的点期望的最小值，即第一次区间选到子集的方案数，考虑有 $x$ 个区间与当前集合有交，那么期望次数 $f = 1 + \frac {m - x} m f$ ，即花费 $1$ 的代价，有 $\frac {m - x} m$ 的概率再来一次，即 $f = \frac m x$ 。那么需要考虑如何计算多少个区间和对于每个集合有交。直接枚举子集的时间复杂度是不可接受的。考虑 DP ，$f _ {i, j}$ 表示考虑 $\{1, 2, \ldots i\}$ 的子集，并且 $i$ 一定在集合内，有 $j$ 个区间有交的容斥系数除以 $j$ 的和，那么可以通过 DP 统计出所有的答案。对于每个 $f _ {i, j}$ ，考虑新加入一个数 $k$ 后增加区间个数，即与 $i$ 无交，但与 $k$ 有交的区间数，可以预处理出来。

查看代码

#include <cstdio>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        flag |= c == '-';
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...Rest>
void read (Type &x, Rest &...y) { read(x); read(y...); }
template <class Type>
void write (Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
}
typedef long long LL;
const int N = 410, mod = 998244353;
int n, m, f[N][N], cnt[N][N];
int binpow (int b, int k = mod - 2)
{
    int res = 1;
    for (; k; k >>= 1, b = (LL)b * b % mod)
        if (k & 1) res = (LL)res * b % mod;
    return res;
}
int main ()
{
    read(n, m);
    for (int i = 1, l, r; i <= m; ++i)
    {
        read(l, r);
        for (int j = 0; j < l; ++j)
            for (int k = l; k <= r; ++k)
                ++cnt[j][k];
    }
    f[0][0] = -1;
    int res = 0;
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
        {
            (res += (LL)m * binpow(j) % mod * f[i][j] % mod) %= mod;
            for (int k = i + 1; k <= n; ++k)
                (f[k][j + cnt[i][k]] -= f[i][j]) %= mod;
        }
    write((res + mod) % mod);
    return 0;
}