C++(g++ 7.5.0) 解法, 执行用时: 94ms, 内存消耗: 432K, 提交时间: 2022-11-11 15:18:49

#include <bits/stdc++.h>
#define fp(i, a, b) for (int i = a, i##_ = int(b); i <= i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = int(b); i >= i##_; --i)

using namespace std;
using ll = long long;
const int P = 998244353;
int inv[11];
void Solve() {
    int n, W, H, m;
    scanf("%d%d%d", &n, &W, &H), m = 1 << n;
    vector<int> lx(n), ly(n), rx(n), ry(n), f(m);;
    fp(i, 0, n - 1) scanf("%d%d%d%d", &lx[i], &ly[i], &rx[i], &ry[i]);
    vector<ll> cap(m), area(m);
    fp(s, 0, m - 1) {
        int x1 = 0, x2 = W, y1 = 0, y2 = H;
        fp(i, 0, n - 1) if (s >> i & 1) {
            x1 = max(x1, lx[i]), y1 = max(y1, ly[i]);
            x2 = min(x2, rx[i]), y2 = min(y2, ry[i]);
        }
        cap[s] = (ll)max(0, x2 - x1) * max(0, y2 - y1);
    }
    fp(s, 1, m - 1)
        for (int t = s; t; t = s & (t - 1))
            area[s] += cap[t] * (__builtin_parity(t) ? 1 : -1);
    
    ll all = (ll)W * H;
    if (area[m - 1] != all)
        return puts("-1"), void();
    fd(s, m - 1, 0) {
        if (area[s] == all) continue;
        ll sum = n;
        fp(i, 0, n - 1) if (~s >> i & 1)
            sum += f[s | 1 << i];
        f[s] = sum % P * inv[n - __builtin_popcount(s)] % P;
    }
    printf("%d\n", f[0]);
}
int main() {
    inv[1] = 1;
    fp(i, 2, 10) inv[i] = (ll)(P - P / i) * inv[P % i] % P;
    int t = 1;
    scanf("%d", &t);
    while (t--) Solve();
    return 0;
}

C++ 解法, 执行用时: 32ms, 内存消耗: 436K, 提交时间: 2022-05-27 12:16:49

#include<bits/stdc++.h>
#define min amin
#define max amax
using namespace std;
using ll=long long;
constexpr int N=1<<10;
constexpr int p=998244353;
int qpow(int x,int n=p-2){int y=1;for(;n;n>>=1,x=1LL*x*x%p)if(n&1)y=1LL*y*x%p;return y;}
template<typename T=int>T read(){T x;cin>>x;return x;}
template<typename U,typename V>auto min(U x,V y){return x<y?x:y;}
template<typename U,typename V>auto max(U x,V y){return x>y?x:y;}

int a[N],b[N],c[N],d[N],ans[N];
ll f[N];
void solve()
{
    int n=read(),s=1<<n;
    cin>>c[0]>>d[0];
    for(int i=1;i<s;i<<=1)cin>>a[i]>>b[i]>>c[i]>>d[i];
    for(int i=0;i<s;++i)
    {
        int j=i&-i,k=i^j;
        a[i]=max(a[j],a[k]);
        b[i]=max(b[j],b[k]);
        c[i]=min(c[j],c[k]);
        d[i]=min(d[j],d[k]);
        if(a[i]<c[i]&&b[i]<d[i])f[i]=1LL*(c[i]-a[i])*(d[i]-b[i]);
        else f[i]=0;
    }
    for(int k=1;k<s;k<<=1)for(int i=0;i<s;++i)if(i&k)f[i]=f[i^k]-f[i];
    if(f[s-1])return cout<<"-1\n",void();
    for(int i=s;i--;)
    {
        if(f[i])
        {
            int x=n,y=0;
            for(int k=0;k<n;++k)if(~i>>k&1)(x+=ans[i^1<<k])%=p,++y;
            ans[i]=1LL*x*qpow(y)%p;
        }
        else ans[i]=0;
    }
    cout<<ans[0]<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(6);
    for(int T=read();T--;solve());
}