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

· · 题解

表示正解为什么是O(4^{n})啊……

明明可以做到O(3^n)啊……

感觉那个dp做法十分奇怪……同时凭借O(2^{n})的空间复杂度拿了rk1？

容斥原理

看到计数想容斥……基本来讲这种玄学的计数题就是容斥定理没跑了……

首先我们发现矩阵中一个点肯定有一个取值范围

范围是[1,min(min(v_{i}),m)]其中i是覆盖了这个点的矩阵，因为呢，如果这个点的取值大过了v的最小值，对应子矩阵的限制就不满足了

然后值域相同的点会连成一些奇形怪状的图案(当然，不一定全部相连)

我们仔细观察这个图形，发现值域不同的点之间的取值无关。

这个是什么意思呢？

如果两个点a,b值域不同的话，a取到值域的max，所满足的子矩阵(们)，和b取到值域的max所满足的子矩阵(们)肯定不同，没有什么既然a取了max那么b就可以随便取了这个说法。

所以a取什么值和b取什么值根本没有任何关系~

那么既然是独立事件就可以使用乘法原理~

因此分别求出每个值域的方案数，最后乘起来就是答案了！

求某一个值域的方案数

(我知道胡乱设一堆变量十分难理解，但是的确不是很好说)

那么我们会发现呢，可能有多个矩阵的值域相同，那么设值域最大值为k的点构成一个集合S_{k}，里面的点可以满足的子矩阵暂且记为1，2，3……号矩阵

那么我们可以先让所有的点随便取，那么总方案数就是k^{|S_{k}|}

然后我们发现明显多算了

所以减去1号子矩阵取不到max的情况，记S_{k}中属于i号矩阵的点构成了集合T_{k,i}那么总方案数为(k-1)^{|T_{k,1}|}k^{|S_{k}|-|T_{k,1}|}，就是属于一号矩阵的点不可以取max，其他的点随便取

然后减去2号子矩阵取不到max的情况，3号子矩阵取不到max的情况，等等……

发现1，2号子矩阵同时取不到max的情况被多减了，所以减去1，2同时取不到max的情况，2，3同时取不到max的情况，1，3同时取不到max的情况……等等

发现此时1，2，3号子矩阵同时取不到max的情况被多加了，所以减去1，2，3同时取不到max的情况，……等等……

然后这样就可以大力容斥出每一个值域的方案数了

大概就是枚举v值相同的矩阵集合的子集，然后加加减减什么的

问题来了，上面要求我们要求出S集合和T集合的siz……

其实就是可以理解成v值相同子矩阵矩阵的并集∪所有值小于当前v的子矩阵并集-所有值小于v的矩阵的并集

T集合的话差不多，就是把上面的“所有”改成子集就可以了，然后就可以求出这个集合的siz了。

问题是如何求出所有并集的siz？

显然所有并集的siz是可以容斥原理暴力做的，直接枚举子集就好……然后O(3^{n})暴力的枚举子集大力容斥就可以了

所以当然非常快了……就酱

上代码~


// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=15;const int M=1050;typedef long long ll;const ll mod=1e9+7;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod){if(p&1){r=r*a%mod;}}return r;}
int n;int m;ll h;ll w;ll s[M];ll u[M];int up;int siz[M];ll res;int T;
struct retc//矩形类 
{
    ll x;ll y;ll x1;ll y1;int v;
    inline void rd(){scanf("%lld%lld%lld%lld%d",&x,&y,&x1,&y1,&v);}
    inline bool ck(){return (x>x1)||(y>y1);}//是否为空 
    inline ll calcs(){return (x1-x+1)*(y1-y+1);}//求面积 
    void operator &=(const retc& a)//交 
    {x=max(x,a.x);y=max(y,a.y);x1=min(x1,a.x1);y1=min(y1,a.y1);}
    friend bool operator <(retc a,retc b){return a.v<b.v;}
}r[N],tr;
inline void solve()
{
    scanf("%lld%lld%d%d",&h,&w,&m,&n);
    for(int i=0;i<n;i++){r[i].rd();}sort(r,r+n);up=(1<<n)-1;
    for(int i=1;i<=up;i++)//暴力求交集面积 
    {
        tr.x=1;tr.y=1;tr.x1=h;tr.y1=w;
        for(int p=i,j=0;p;p>>=1,j++){if(p&1){tr&=r[j];if(tr.ck()){s[i]=0;goto ed;}}}
        s[i]=tr.calcs();ed:;
    }
    for(int i=1;i<=up;i++)//暴力求并集面积 
    {
        for(int j=i;j;j=(j-1)&i)
        {if(siz[j]%2){u[i]+=s[j];}else {u[i]-=s[j];}}
    }
    int ns=0;int ls=0;res=1;
    for(int i=0;i<n;i++)//分值域统计方案数 
    {
        ns|=(1<<i);if(r[i].v==r[i+1].v){continue;}
        ll tot=u[ns|ls]-u[ls];ll st=tot;ll ret=po(r[i].v,tot);
        for(int k=ns;k;k=(k-1)&ns)
        {
            tot=u[k|ls]-u[ls];
            ll del=po(r[i].v-1,tot)*po(r[i].v,st-tot)%mod;
            if(siz[k]%2){ret=(ret+mod-del)%mod;}
            else {ret=(ret+del)%mod;}
        }res=res*ret%mod;ls|=ns;ns=0;//乘起来  
    }printf("%lld\n",res*po(m,h*w-u[up])%mod); 
}
inline void clear(){for(int i=0;i<=up;i++){u[i]=0;}}
int main()
{
    for(int i=1;i<=1023;i++){siz[i]=siz[i>>1]+(i&1);}scanf("%d",&T);
    for(int z=1;z<=T;z++){solve();clear();}return 0;//拜拜程序~ 
}