ICPC2022KunMingB

题目大意

给定一个\(W*H\)的方格矩阵。和\(n\)的小方格阵，每个覆盖了左下角为\(x_{i1},y_{i1}\)，右上角为\(x_{i2},y_{i2}\)的方格。

每一步会等概率随机选择一个方格阵(包括被染色的)，把它全部涂黑，问把\(W*H\)的方格矩阵全部涂黑的期望步数是多少？ 题目链接 ## 思路 考虑一个简化模型，\(n\)个方块，每次等概率随机染黑一个，问期望步数是多少？

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

那么已经染黑了\(i\)个的情况下，有\(\frac{n - i}{n}\)的概率选择一个没有被染黑的，有\(\frac{i}{n}\)选择了一个已经被染黑的方块 即\(f[i] = 1+ \frac{n - i}{n}*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}*f[i] + \frac{1}{n}\sum f[i << (1<<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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/04/24/ICPC2022KunMingB/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！