【ICPC】2022 昆明站 B题 题解

题目大意

给定一个 $W \times H$ 的方格矩阵，和 $n$ 个小方格阵，每个覆盖了左下角为 $(x_{i1}, y_{i1})$、右上角为 $(x_{i2}, y_{i2})$ 的区域。每一步会等概率随机选择一个方格阵（包括被染色的），把它全部涂黑，问把 $W \times H$ 的方格矩阵全部涂黑的期望步数是多少？

题目链接

思路

考虑一个简化模型，$n$ 个方块，每次等概率随机染黑一个，问期望步数是多少？

设 $f[i]$ 为已经染黑了 $i$ 个方格后，再全部染黑的期望步数。

那么已经染黑了 $i$ 个的情况下，有 $\frac{n-i}{n}$ 的概率染到新格子，$\frac{i}{n}$ 的概率染到已有格子，即

$$f[i] = 1 + \frac{n-i}{n} \cdot f[i+1] + \frac{i}{n} f[i]$$

化简后

$$f[i] = \frac{n}{n-i} + f[i+1]$$

这个式子也可以感性理解，如果每次都能选到未被涂黑的格子，那么 $f[i] = 1 + f[i+1]$，但事实上未必每次都会选到，所以需要额外花费几次。

那么这一题也是这种思路，只不过此时的 $i$ 是状态压缩含义，表示选择了哪些方格阵。

$$f[i] = \frac{i.count}{n} \cdot f[i] + \frac{1}{n} \sum_j f[i \mid (1 \ll j)]$$

其中 $i.count$ 是 $i$ 中 $1$ 的个数（即已经染过的方格阵），$j$ 是未被染黑的方格阵。

由于坐标较大，所以我们需要离散化点的坐标。

而且为了防止常数过大，用 bitset 代替了离散后的矩阵（每一位的 $0, 1$ 代表这个格子有没有被染色）。

我们保存一下每一个方格阵会染色哪些方格，然后就 dfs 遍历所有状态。

代码

#include <cstdio>
#include <iostream>
#include <bitset>
#include <algorithm>
#include <cstring>
using namespace std;

const long long  Mod = 998244353;
int T, n, W, H, sx[25], sy[25], cntx, cnty, k;

long long inv[25], f[1 << 11];

bitset<500> mask[12], state, tmp; //mask是每个方格阵能够染色哪些方格

struct Rect {
    pair<int, int> l, r;
}rect[15];

inline long long qpow(long long a, long long b)
{
    long long res = 1;
    while(b) {
        if(b & 1)
            res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

void dfs(int u, int s)
{
    if(u == n + 1) {
        f[s] = state.count() == k ? 0 : -1;
        return ;
    }
    bitset<500> t = state;
    dfs(u + 1, s);
    state = t;
    state |= mask[u];
    dfs(u + 1, s | (1 << (u - 1)));
}

int main()
{
    for(int i = 1; i <= 20; ++i) 
        inv[i] = qpow(i, Mod - 2);;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        scanf("%d%d", &W, &H);
        cntx = cnty = 0;
        memset(f, 0, sizeof f);
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d%d%d", &rect[i].l.first, &rect[i].l.second, &rect[i].r.first, &rect[i].r.second);
            rect[i].l.first = min(rect[i].l.first, W); rect[i].l.second = min(rect[i].l.second, H);
            rect[i].r.first = min(rect[i].r.first, W); rect[i].r.second = min(rect[i].r.second, H);
            sx[++cntx] = rect[i].l.first; sx[++cntx] = rect[i].r.first;
            sy[++cnty] = rect[i].l.second; sy[++cnty] = rect[i].r.second;
        }
        sort(sx + 1, sx + 1 + cntx); sort(sy + 1, sy + 1+ cnty);
        cntx = unique(sx + 1, sx + 1 + cntx) - (sx + 1);
        cnty = unique(sy + 1, sy + 1 + cnty) - (sy + 1);
        k = (cntx - 1) * (cnty - 1);
        for(int i = 1; i <= n; ++i) {
            rect[i].l.first = lower_bound(sx + 1, sx + 1 + cntx, rect[i].l.first) - sx;
            rect[i].l.second = lower_bound(sy + 1, sy + 1 + cnty, rect[i].l.second) - sy;
            rect[i].r.first = lower_bound(sx + 1, sx + 1 + cntx, rect[i].r.first) - sx;
            rect[i].r.second = lower_bound(sy + 1, sy + 1 + cnty, rect[i].r.second) - sy;
            mask[i].reset(); tmp.reset();
            tmp = (1 << (rect[i].r.second - rect[i].l.second)) - 1;
            tmp <<= rect[i].l.second - 1;
            for(int j = rect[i].l.first - 1; j < rect[i].r.first - 1; ++j)
                mask[i] |= (tmp << (j * cnty));
        }
        state.reset();
        dfs(1, 0);
        if(f[(1 << n) - 1] == -1) {
            printf("-1\n");
            continue;
        }
        for(int i = (1 << n) - 1; i >= 0; --i) {
            if(f[i] != -1)
                continue;
            int cnt = 0; 
            long long res = 0;
            for(int j = 1; j <= n; ++j) {
                if((i >> (j - 1)) & 1) 
                    cnt++;
                else 
                    res = (res + 1LL * inv[n] * f[i | (1 << (j - 1))]) % Mod; 
            }
            f[i] = (((1LL + res) * n) % Mod * inv[n - cnt]) % Mod; 
        }
        printf("%lld\n", f[0]);
    }
    return 0;
}