B Blocks

https://ac.nowcoder.com/acm/contest/32708/B

We first perform binary compression on each rectangle , state $i$ Each bit of represents a rectangle , This position is $1$ Indicates that this rectangle has been selected , Otherwise, there is no choice .

Then we set $f[i]$ Indicates that the current state is $i$ , How many more steps do we need to take （ expect ）, Before you can put the whole big rectangle $WH$ fill . that $f[0]$ It's the answer we're asking for .

At this time, we can solve two cases ：

（1） state $i$ The large rectangle has been $WH$ fill , So we have ：
$$f[i]=0$$
（2） state $i$ The large rectangle has not been $WH$ fill , Then let's consider the next possible choice at this time , Obviously, we have $n$ A choice . that $n$ The two options can also be divided into two cases ：

① If we choose a rectangle $j$ And $j$ It's state $i$ A rectangle that has been selected （ namely $(i>>j\&1=1)$ ）, Then the expected number of steps is still $f[i]$ .

② If the selected rectangle $j$ Does not exist in $i$ in （ namely $(i>>j\&1=0)$ ）, So in choosing $j$ The expected number of steps after that is $f[i\oplus (1<<j)]$ .

So let's set up ：

$cnt=shapestateiinhasthechooseChoose了OfMomentshapeOfindividualCount$

$c=\sum _{i>>j\&1=0}f[i\oplus (1<<j)]$

We can get the equation （ Among them $1$ In order to reach the next state, you must choose the next step , The next two fractions correspond to each other ① And circumstances ②）：
$$f[i]=1+\frac{cnt\times f[i]}{n}+\frac{c}{n}$$
After finishing, there is ：
$$f[i]=\frac{n+c}{n-cnt}$$

Then we can find , Enumerate in reverse order $i$ You can roll out all $f[i]$ , Until you get the answer $f[0]$ .

So now there is a big problem is how to know the status $i$ Whether the rectangle in the can cover the whole $WH$ , Here we divide each area into $1$ The small rectangle is treated as an element , So the given $n$ A rectangle can be regarded as $n$ A collection of , So now we are actually asking for the union of several sets, set size , Then we can use the intersection size of its subsets to find the size of the union set , The intersection size of subsets is actually the area intersection of several rectangles , Here we maintain four boundaries to obtain . The time complexity of doing this is $O(3^N)$ , Of course we can pass it $SOSDP$ Optimize the time complexity to $O(2^{N}N)$ .

$code1$ （ Not optimized , Directly enumerate subsets , In the code $area[i]$ Represents the state $i$ The area of , $dp[i]$ Represents the state $i$ Area and ）：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 12;
const ll mod = 998244353;

ll ksm(ll base, ll n) {
    
    ll ans = 1;
    while(n) {
    
        if (n & 1ll) ans = ans * base % mod;
        base = base * base % mod;
        n >>= 1ll;
    }
    return ans;
}

int n;
int x[N], y[N], xx[N], yy[N], W, H;
ll dp[1 << N], area[1 << N], f[1 << N], inv[N];

int main() {
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    for (int i = 1; i <= 10; ++i) inv[i] = ksm(i, mod - 2);
    int T; scanf("%d", &T);
    while(T--) {
    
        scanf("%d%d%d", &n, &W, &H);
        for (int i = 0; i < n; ++i) {
    
            scanf("%d%d%d%d", &x[i], &y[i], &xx[i], &yy[i]);
        }
        for (int i = 1; i < (1 << n); ++i) {
    
            int xl = 0, yl = 0, xr = W, yr = H;
            for (int j = 0; j < n; ++j) {
    
                if (i >> j & 1) {
    
                    xl = max(xl, x[j]);
                    xr = min(xr, xx[j]);
                    yl = max(yl, y[j]);
                    yr = min(yr, yy[j]);
                }
            }
            area[i] = 1ll * max(0, (xr - xl)) * max(0, (yr - yl));
        }
        for (int i = 1; i < (1 << n); ++i) {
    
            dp[i] = 0;
            for (int s = i; s; s = (s - 1) & i) {
    
                dp[i] += area[s] * (__builtin_parity(s) ? 1 : -1);
            }
        }
        ll SS = W * H;
        if (dp[(1 << n) - 1] != SS) {
    
            puts("-1");
            continue;
        }
        for (int i = (1 << n) - 1; i >= 0; --i) {
    
            f[i] = 0;
            if (dp[i] == SS) continue;
            ll csum = 0;
            for (int j = 0; j < n; ++j) {
    
                if (!(i >> j & 1)) {
    
                    csum = (csum + f[i ^ (1 << j)]) % mod;
                }
            }
            f[i] = (n + csum) * inv[n - __builtin_popcount(i)] % mod;
        }
        printf("%lld\n", f[0]);
    }
}

$code2$（$SOSDP$ Optimize ）：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 12;
const ll mod = 998244353;

ll ksm(ll base, ll n) {
    
    ll ans = 1;
    while(n) {
    
        if (n & 1ll) ans = ans * base % mod;
        base = base * base % mod;
        n >>= 1ll;
    }
    return ans;
}

int n;
int x[N], y[N], xx[N], yy[N], W, H;
ll dp[1 << N], area[1 << N], f[1 << N], inv[N];

int main() {
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    for (int i = 1; i <= 10; ++i) inv[i] = ksm(i, mod - 2);
    int T; scanf("%d", &T);
    while(T--) {
    
        scanf("%d%d%d", &n, &W, &H);
        for (int i = 0; i < n; ++i) {
    
            scanf("%d%d%d%d", &x[i], &y[i], &xx[i], &yy[i]);
        }
        for (int i = 1; i < (1 << n); ++i) {
    
            int xl = 0, yl = 0, xr = W, yr = H;
            for (int j = 0; j < n; ++j) {
    
                if (i >> j & 1) {
    
                    xl = max(xl, x[j]);
                    xr = min(xr, xx[j]);
                    yl = max(yl, y[j]);
                    yr = min(yr, yy[j]);
                }
            }
            area[i] = 1ll * max(0, (xr - xl)) * max(0, (yr - yl));
        }

        for (int j = 0; j < (1 << n); ++j) {
    
            dp[j] = area[j] * (__builtin_parity(j) ? 1 : -1);
        }
        for (int i = 0; i < n; ++i) {
    
            for (int j = 0; j < (1 << n); ++j) {
    
                if (j >> i & 1) {
    
                    dp[j] += dp[j ^ (1 << i)];
                }
            }
        }
        ll SS = W * H;
        if (dp[(1 << n) - 1] != SS) {
    
            puts("-1");
            continue;
        }
        for (int i = (1 << n) - 1; i >= 0; --i) {
    
            f[i] = 0;
            if (dp[i] == SS) continue;
            ll csum = 0;
            for (int j = 0; j < n; ++j) {
    
                if (!(i >> j & 1)) {
    
                    csum = (csum + f[i ^ (1 << j)]) % mod;
                }
            }
            f[i] = (n + csum) * inv[n - __builtin_popcount(i)] % mod;
        }
        printf("%lld\n", f[0]);
    }
}