题解 P3813 【[FJOI2017]矩阵填数】

· · 题解

一、题目

点此看题

二、解法

观察数组范围，发现h,w特别大，而限制只有至多10条，我们考虑离散化。

怎么个离散化法呢？考虑将每一个限制的四个边延长，这样就将大矩形切割成了至多20\times 20个小矩形，且这些小矩形的性质是一样的（被哪些限制包含）。 具体的离散化操作我们把它当做切木棍，对于[l,r]，我们这样离散化：

也就是我们把l，r各切一刀，在l加上一个左括号，l-1加上一个右括号，r加上一个左括号，r+1加上一个右括号，离散化就变成了括号匹配问题，排序后匹配相邻的括号即可。

离散化后，我们发现每个限制中只要中只要有一个小矩形满足限制就可以了，由于限制数很小，考虑状态压缩，设dp[i][s]为前i个小矩形满足状压后为s的条件的方案数，我们先考虑每一个小矩形：

中间的那个小矩形被两个限制所包含，但是我们只能满足要求最大值为3的限制，所以我们记小矩形的状态为10（二进制），dp时拿原状态或上小矩形的状态就可以得到目标状态。我们再记g[i]=(Min-1)^s（s为小矩形的面积），即无法满足任何一个限制的情况，f[i]=Min^{s}-g[i]为能满足最大值最小的限制的情况（我们也只能满足这些限制），那样我们就能写出如下dp方程（记小矩形状态为S）：

dp[i][j|S]=dp[i-1][j]\times f[i] \\ dp[i][j]=dp[i-1][j]\times g[i] \end{cases}

最后输出dp[m][2^n-1]即可（m是小矩形的个数），时间复杂度O(4n^{2}\times 2^n)。

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int MOD = 1e9+7;

const int MAXN = 10005;
int read()
{
    int x=0,flag=1;char c;
    while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*flag;
}
int T,h,w,m,n,cnt,oth,dp[505][1<<10];
int x1[MAXN],y1[MAXN],x2[MAXN],y2[MAXN],v[MAXN];
bool vx[MAXN][2],vy[MAXN][2];
vector<pair<int,int> > x,y;
struct node
{
    int f,g,s;
}a[505];
void add(int z,bool d,bool type)
{
    if(!type) x.push_back(make_pair(z,d)),vx[z][d]=1;
    else y.push_back(make_pair(z,d)),vy[z][d]=1;
}
int qkpow(int a,int b)
{
    int res=1;
    while(b>0)
    {
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}
signed main()
{
    T=read();
    while(T--)
    {
        h=read();w=read();m=read();n=read();
        cnt=oth=0;
        memset(vx,0,sizeof vx);
        memset(vy,0,sizeof vy);
        memset(dp,0,sizeof dp);
        x.clear();y.clear();
        add(1,0,0);add(h,1,0);
        add(1,0,1);add(w,1,1);
        for(int i=1;i<=n;i++)
        {
            x1[i]=read();y1[i]=read();x2[i]=read();y2[i]=read();v[i]=read();
            if(x1[i]>1 && !vx[x1[i]-1][1])
                add(x1[i]-1,1,0);
            if(!vx[x1[i]][0])
                add(x1[i],0,0);
            if(x2[i]<h && !vx[x2[i]+1][0])
                add(x2[i]+1,0,0);
            if(!vx[x2[i]][1])
                add(x2[i],1,0);
            if(y1[i]>1 && !vy[y1[i]-1][1])
                add(y1[i]-1,1,1);
            if(!vy[y1[i]][0])
                add(y1[i],0,1);
            if(y2[i]<w && !vy[y2[i]+1][0])
                add(y2[i]+1,0,1);
            if(!vy[y2[i]][1])
                add(y2[i],1,1);
        }
        sort(x.begin(),x.end());
        sort(y.begin(),y.end());
        for(int i=0;i<x.size();i+=2)
            for(int j=0;j<y.size();j+=2)
            {
                int a1=x[i].first,a2=x[i+1].first;
                int b1=y[j].first,b2=y[j+1].first;
                int siz=(a2-a1+1)*(b2-b1+1),s=0,Min=m;
                for(int k=1;k<=n;k++)
                {
                    if(a1>=x1[k] && a2<=x2[k] && b1>=y1[k] && b2<=y2[k])
                    {
                        if(Min>v[k])
                        {
                            Min=v[k];
                            s=0;
                        }
                        if(Min==v[k]) s|=(1<<k-1);
                    }
                }
                int g=qkpow(Min-1,siz),f=qkpow(Min,siz)-g;
                if(!s) oth+=siz;
                else  a[++cnt]=node{f,g,s};
            }
        dp[0][0]=1;
        for(int i=1;i<=cnt;i++)
        {
            for(int j=0;j<(1<<n);j++)
                dp[i][j|a[i].s]=(dp[i][j|a[i].s]+dp[i-1][j]*a[i].f)%MOD;
            for(int j=0;j<(1<<n);j++)
                dp[i][j]=(dp[i][j]+dp[i-1][j]*a[i].g)%MOD;
        }
        printf("%d\n",(dp[cnt][(1<<n)-1]*qkpow(m,oth)%MOD+MOD)%MOD);
    }
}