题解：P3813 [FJOI2017] 矩阵填数

· · 题解

更好的阅读体验

注意到，一个矩阵最大值为 x 的充要条件是：

仅考虑第一个条件是好做的。具体地，每一个格子存在一个取值的上限 mx_{i, j}，也就是所有覆盖这个格子矩形的 v 的最小值。由于不同格子是独立的，所以答案就是

\prod_{i = 1}^{h}\prod_{j=1}^{w}mx_{i, j}

接下来加上第二个条件不好做，考虑把不符合条件的填数字方案给容斥掉。

由于 n 很小，我们钦定一个集合 S 内的矩形不符合第二个条件，别的矩形无所谓。那么我们就可以这么求这个 mx，其中 \leftarrow 表示取最小值：

mx_{i, j} \leftarrow v_k(k \not \in S, (i, j) \in \operatorname{rectangle}_k) mx_{i, j} \leftarrow v_k-1 (k \in S, (i, j) \in \operatorname{rectangle}_k)

第二个式子之所以要 -1 是因为我们希望每个格子都不取到上界。

设 f_S 为钦定集合 S 求出的答案，再假设 g_S 表示恰好只有集合 S 不满足条件所求出的答案。由定义，f_S 就是所有 S 的超集 T 的 g_T 之和。

f_S = \sum_{S \sube T} g_T

子集反演。

g_T = \sum_{S \sube T} (-1)^{|T| - |S|}f_S \operatorname{ans} = g_{\varnothing} = \sum_{T}(-1)^{|T|}f_{T}

然后这道题就做完了。注意到我们有用的行和列只有矩形的边所在的行和列，所以可以离散化一下，这样我们暴力进行一次矩形修改的复杂度可以做到 O(n^2)，枚举子集再枚举矩形，复杂度为 O(2^n n^3)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 41
#define MOD 1000000007
using namespace std;
int h,w,m,n,ans,bnx,bny,bx[N],by[N],l[N],r[N],u[N],d[N],val[N],mx[N][N];
int qpow(int x,int y=MOD-2)
{
    int ret=1;
    for(;y;x=x*x%MOD,y>>=1)if(y&1)ret=ret*x%MOD;
    return ret;
}
void lsh(int &bn,int *b,int lim,int *x,int *y)
{
    bn=0,b[++bn]=1,b[++bn]=lim+1;
    for(int i=0;i<n;i++)b[++bn]=x[i],b[++bn]=y[i]+1;
    sort(b+1,b+1+bn),bn=unique(b+1,b+1+bn)-b-1;
    for(int i=0;i<n;i++)x[i]=lower_bound(b+1,b+1+bn,x[i])-b;
    for(int i=0;i<n;i++)y[i]=lower_bound(b+1,b+1+bn,y[i]+1)-b-1;
}
void solve()
{
    scanf("%lld%lld%lld%lld",&h,&w,&m,&n),ans=0;
    for(int i=0;i<n;i++)
        scanf("%lld%lld%lld%lld%lld",&u[i],&l[i],&d[i],&r[i],&val[i]);
    lsh(bnx,bx,h,u,d),lsh(bny,by,w,l,r);
    for(int S=0;S<(1<<n);S++)
    {
        int sum=1;
        for(int i=1;i<=bnx;i++)
            for(int j=1;j<=bny;j++)mx[i][j]=m;
        for(int i=0;i<n;i++)
            for(int j=u[i];j<=d[i];j++)
                for(int k=l[i];k<=r[i];k++)mx[j][k]=min(mx[j][k],val[i]-(S>>i&1));
        for(int i=1;i<bnx;i++)
            for(int j=1;j<bny;j++)sum*=qpow(mx[i][j],(bx[i+1]-bx[i])*(by[j+1]-by[j])),sum%=MOD;
        if(__builtin_popcountll(S)&1)ans+=MOD-sum;
        else ans+=sum; ans%=MOD;
    }
    printf("%lld\n",ans);
}
main()
{
    int T;scanf("%lld",&T);
    while(T--)solve();
    return 0;
}