LINK：矩阵填数
刚看到题目的时候感觉是无从下手的。
可以看到有n<=2的点 两个矩形。
如果只有一个矩形 矩形外的方案数容易计算考虑 矩形内的 必须要存在x这个最大值 且所有值<=x.
直接计算是不易的 需要讨论到底哪个位置有最大值 然后还有重复 很繁琐。可以直接容斥 可以求出<=x的方案数 <=x-1的方案数也可以求出 做差即可得到存在x出现的方案数。
考虑两个矩形 如果不交 那么显然是各算各的 如果相交 讨论相交的这部分到底存在x 然后进一步的讨论从而计算答案。
可以发现这个分类讨论并不繁琐 不过当n扩大的时候就不能这么做了。
在填数的时候 毫无疑问的是 把一些矩形的交拉出来单独讨论。因为这部分填数会对一些矩形后续的填数造成影响。
对于所有的这种面积求方案即可。n<=10 可以进行状压。
设f[i]表示 只有状态i的矩形进行交的面积 注意 他们的交不能和其他矩形再交 因为 这会影响到其他矩形。
求法：容斥 考虑先把大的交w就出来 对于w的子集显然也会统计到这部分答案 所以枚举子集一下将自己的这部分贡献给消掉即可。
把这些面积拉出来后 就可以尝试填数了 容易发现填数的时候 可以设状态j表示当前已经满足的矩形的状态。
这样对于所有的交dp一下就可以得到总方案数了
const int MAXN=15,N=1<<10;
int T,n,W,H,m;
int maxx;
int w[MAXN];
struct wy
{
int x,y,xx,yy;
wy(int s1=0,int s2=0,int s3=0,int s4=0){x=s1;y=s2;xx=s3;yy=s4;}
inline wy friend operator &(wy a,wy b)//两个矩形的交.
{
return wy(max(a.x,b.x),max(a.y,b.y),min(a.xx,b.xx),min(a.yy,b.yy));
}
inline int S()
{
if(x>xx||y>yy)return 0;
return (xx-x+1)*(yy-y+1);
}
}t[MAXN];
inline int ksm(int b,int p)
{
int cnt=1;
while(p){if(p&1)cnt=(ll)cnt*b%mod;b=(ll)b*b%mod;p=p>>1;}
return cnt;
}
int ans,f[N][N];//f[i][j]表示已经处理过集合为1~i 已经满足限制的集合为j的方案数.
int s[N],b[N],c[N],s1[N],s2[N];
signed main()
{
freopen("1.in","r",stdin);
get(T);
while(T--)
{
memset(f,0,sizeof(f));
memset(s,0,sizeof(s));
get(H);get(W);get(m);get(n);ans=0;
rep(1,n,i)
{
int get(x),get(y),get(xx),get(yy);
t[i]=wy(x,y,xx,yy),get(w[i]);
}
maxx=(1<<n)-1;
fep(maxx,1,i)
{
int minn=m,ww=0;
wy wn=wy(1,1,H,W);
rep(1,n,j)
if(i&(1<<(j-1)))
{
if(w[j]==minn)ww=ww|(1<<(j-1));
if(w[j]<minn)
{
minn=w[j];
ww=(1<<(j-1));
}
wn=wn&t[j];
}
int ss=wn.S();
s[i]+=ss;c[i]=ww;
for(int j=i&(i-1);j;j=i&(j-1))s[j]-=s[i];
ans+=s[i];
s2[i]=ksm(minn-1,s[i]);
s1[i]=(ksm(minn,s[i])-s2[i]+mod)%mod;
}
ans=W*H-ans;ans=ksm(m,ans);
f[0][0]=1;
rep(0,maxx-1,i)
{
rep(0,maxx,j)
{
if(!f[i][j])continue;
f[i+1][j]=(f[i+1][j]+(ll)f[i][j]*s2[i+1])%mod;
f[i+1][j|c[i+1]]=(f[i+1][j|c[i+1]]+(ll)f[i][j]*s1[i+1])%mod;
}
}
put((ll)f[maxx][maxx]*ans%mod);
}
return 0;
}