传送门
这题其实在容斥那一部分还是比较好想的。首先很快的可以发现，矩阵中不同值域的格子会连成一个个不规则区域，而且不同值域的格子互不影响，那么我们可以单独计算每种值域构成的区域的情况，之后用乘法原理乘起来就是答案。
因为有一些值域可能同时包含多个矩形，所以我们要用容斥，先强制一个矩形不能取max，再两个……这样就可以计算出来了。
于是乎现在我的一种暴力思路是求出各个不同值域矩形的面积。然后我发现我不会求……
于是学了一招。我们把满足矩阵限制的情况压成一个二进制数，用(u[i])表示在满足限制i的情况下的格子数。之后对于求每个i的矩形格子数，我们首先暴力求所有矩形的交并且计算答案，在求并的时候只要枚举子集并使用容斥原理就可以计算了。
计算答案的时候与之类似，按值域从小到大枚举矩形，之后使用容斥原理计算这一部分的答案是多少，所有的都乘起来就好了。中间使用了位运算的方法来快速求出符合当前限制的有多少个格子，之后用快速枚举子集的方法计算容斥。复杂度(O(3^n))
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')
#define fr friend inline
#define y1 poj
#define mp make_pair
#define pr pair<int,int>
#define fi first
#define sc second
#define pb push_back
using namespace std;
typedef long long ll;
const int M = 10005;
const ll mod = 1e9+7;
const double eps = 1e-7;
ll read()
{
ll ans = 0,op = 1;char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}
while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();
return ans * op;
}
ll T,h,w,m,n,sum,s[2005],size[2005],u[2005],res;
int ns,ls;
ll inc(ll a,ll b){return (a+b) % mod;}
ll mul(ll a,ll b){return a * b % mod;}
ll qpow(ll a,ll b)
{
ll p = 1;
while(b)
{
if(b & 1) p = mul(p,a);
a = mul(a,a),b >>= 1;
}
return p;
}
struct matrix
{
ll x1,x2,y1,y2,v;
bool empty(){return (x1 > x2) || (y1 > y2);}
ll cal(){return (x2-x1+1) * (y2-y1+1);}
void operator &= (const matrix &a){x1 = max(x1,a.x1),x2 = min(x2,a.x2),y1 = max(y1,a.y1),y2 = min(y2,a.y2);}
bool operator < (const matrix &a){return v < a.v;}
}r[15],mat;
int main()
{
rep(i,1,1<<10) size[i] = size[i>>1] + (i&1);
T = read();
while(T--)
{
h = read(),w = read(),m = read(),n = read();
rep(i,1,n) r[i].x1 = read(),r[i].y1 = read(),r[i].x2 = read(),r[i].y2 = read(),r[i].v = read();
sort(r+1,r+n+1),sum = (1<<n) - 1;
rep(i,1,sum)//矩形面积交集
{
bool flag = 1;
mat.x1 = mat.y1 = 1,mat.x2 = h,mat.y2 = w;
for(int p = i,j = 1;p;p >>= 1,j++)
{
if(p & 1) mat &= r[j];
if(mat.empty()) {s[i] = 0,flag = 0;break;}
}
if(flag) s[i] = mat.cal();
}
rep(i,1,sum) for(int j = i;j;j = (j-1) & i) (size[j] & 1) ? u[i] += s[j] : u[i] -= s[j];//矩形面积并集
ns = ls = 0,res = 1;
rep(i,1,n)
{
ns |= (1<<(i-1));//表示当前取到的所有限制
if(r[i].v == r[i+1].v) continue;
ll tot = u[ns|ls] - u[ls],st = tot,ret = qpow(r[i].v,tot);//减去之前的限制，只留下现在的
for(int k = ns;k;k = (k-1) & ns)//快速枚举子集用容斥计算
{
tot = u[k|ls] - u[ls];
ll det = mul(qpow(r[i].v-1,tot),qpow(r[i].v,st - tot));
(size[k] & 1) ? ret = inc(ret,mod-det) : ret = inc(ret,det);
}
res = mul(res,ret),ls |= ns,ns = 0;
}
printf("%lld
",mul(res,qpow(m,h*w-u[sum])));
rep(i,0,sum) u[i] = 0;
}
return 0;
}