题解：P3813 [FJOI2017] 矩阵填数

· · 题解

思路

我们分析发现子矩阵之间的相互影响很重要，也不好处理。但是注意到权值小的子矩阵填完后一定不会影响权值大的子矩阵的答案。

于是考虑按照值域从小到大依次考虑每一个权值方案，做乘法原理即可。

问题转化为相同权值的一些子矩阵，满足每一个子矩阵的值不超过 V 同时至少存在一个权值为 V 的位置。不超过 V 这一限制只要限定选数的值域容易满足。至少存在一个权值为 V 的位置这一限制不容易满足，但容易打破，考虑容斥。

我们钦定一些矩阵不存在权值为 V，做子集容斥即可，系数取决于子集大小。 本题需要离散化。注意此题目中坐标代表的是格子而不是点，因此我们记录左闭右开的区间 [l,r+1)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int T;
int H,W,n,m;
struct Matrix{
    int lx,ly,rx,ry,v;
}Mat[15];
bool cmp(Matrix aa,Matrix bb){
    return aa.v<bb.v;
}
int x[35],y[35];
int siz[55][55];
int lim[55][55];
bool vis[55][55];
int qp(int x,int p){
    int res=1;
    while(p){
        if(p&1)res=res*x%mod;
        x=x*x%mod;
        p>>=1; 
    } 
    return res;
}
vector<int>vec;
int tot1,tot2;
int solve(int V,int sum){
    int num=vec.size();
    int ans=0;
    for(int S=0;S<(1<<num);S++){
        int ct=0;
        int k=__builtin_popcount(S);
        for(int px=1;px<tot1;px++){
            for(int py=1;py<tot2;py++){
                if(lim[px][py]!=V)continue;
                for(int i=0;i<num;i++){
                    if((1<<i)&S){
                        if(px>=Mat[vec[i]].lx&&px<Mat[vec[i]].rx&&py>=Mat[vec[i]].ly&&py<Mat[vec[i]].ry){
                            ct+=siz[px][py];
                            break;
                        }
                    }
                }
            }
        }
        int res=qp(V-1,ct)*qp(V,sum-ct)%mod;
        if(k&1)ans=(ans-res+mod)%mod;
        else ans=(ans+res)%mod;
    } 
    return ans;
}
signed main(){
    cin>>T;
    while(T--){
        memset(vis,0,sizeof(vis));
        memset(lim,0,sizeof(lim));
        memset(siz,0,sizeof(siz)); 
        cin>>H>>W>>m>>n;
        for(int i=1;i<=n;i++){
            int lx,ly,rx,ry,v;
            cin>>lx>>ly>>rx>>ry>>v;
            x[i]=lx,x[i+n]=rx+1;
            y[i]=ly,y[i+n]=ry+1;
            Mat[i]={lx,ly,rx+1,ry+1,v};
        }
        sort(x+1,x+1+n*2);
        sort(y+1,y+1+n*2);
        tot1=unique(x+1,x+1+n*2)-x-1;
        tot2=unique(y+1,y+1+n*2)-y-1;
        sort(Mat+1,Mat+n+1,cmp);
        for(int i=1;i<=n;i++){
            Mat[i].lx=lower_bound(x+1,x+1+tot1,Mat[i].lx)-x;
            Mat[i].ly=lower_bound(y+1,y+1+tot2,Mat[i].ly)-y;
            Mat[i].rx=lower_bound(x+1,x+1+tot1,Mat[i].rx)-x;
            Mat[i].ry=lower_bound(y+1,y+1+tot2,Mat[i].ry)-y;
        }
        int cnt=0,ans=1;
        int num=H*W;
        int tt=0;
        for(int i=1;i<=n;i++){
            int ct=0;
            for(int px=Mat[i].lx;px<Mat[i].rx;px++){
                for(int py=Mat[i].ly;py<Mat[i].ry;py++){
                    //cout<<px<<" "<<py<<"\n";
                    if(vis[px][py])continue;
                    vis[px][py]=1;
                    lim[px][py]=Mat[i].v;
                    siz[px][py]=(x[px+1]-x[px])*(y[py+1]-y[py]);
                    ct+=siz[px][py];
                }
            }
            vec.push_back(i);
            cnt+=ct;
            if(i==n||Mat[i+1].v!=Mat[i].v){
                ans=ans*solve(Mat[i].v,cnt)%mod; 
                num-=cnt;
                cnt=0;
                vec.clear();
            }
        }
        ans=ans*qp(m,num)%mod;
        cout<<ans<<"\n";
    }
    return 0;
}