shadowice1984说:看到计数想容斥........
这题中,我们把图分成若干块,每块的最大值域不同
蓝后根据乘法原理把每块的方案数(互不相干)相乘。
怎么计算每块方案数呢
把子矩阵按最大值从小到大排序
暴力预处理好每$k(1<=k<=n)$个矩阵之间的交集、并集
设最大值为$v$的位置的集合大小为$S$
那么我们算出来(本层)的结果就是v^{|S|}
然鹅我们并没有减去某些矩阵没有到最大值(最大只取到$v-1$)的情况
于是对于每个最大值为$v$的子矩阵在$S$中的部分$T$,我们要减去$(v-1)^{|T|}*v^{|S-T|}$
但是我们又发现,多减去了某2个子矩阵都没有到最大值的情况,于是我们就把它加起来
再减去3个子矩阵都没到最大值的情况
.............
这就是容斥原理辣
“最大值为$v$的位置的集合大小为$S$”,这个咋算呢
$|S|=($最大值$<=v$的位置的集合大小)$-$(最大值$<v$的集合大小),$T$同理。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+;
inline ll Min(ll a,ll b){return a<b?a:b;}
inline ll Max(ll a,ll b){return a>b?a:b;}
ll Pow(ll x,ll y){
ll re=;
for(;y;y>>=,x=x*x%mod)
if(y&) re=re*x%mod;
return re;
}
struct Matrix{
ll xl,yl,xr,yr,v;
bool operator < (const Matrix &tmp) const{return v<tmp.v;}
void operator &= (const Matrix &tmp) {
xl=Max(xl,tmp.xl), xr=Min(xr,tmp.xr);
yl=Max(yl,tmp.yl), yr=Min(yr,tmp.yr);
}
inline void init(){
scanf("%lld%lld%lld%lld%lld",&xl,&yl,&xr,&yr,&v);
}
inline bool null(){return xl>xr||yl>yr;}
inline ll area(){return (xr-xl+)*(yr-yl+);}
}a[],p;
int T,m,n,uni[],ist[],siz[];ll h,w;
void Solve(){
memset(uni,,sizeof(uni));
scanf("%lld%lld%d%d",&h,&w,&m,&n);
for(int i=;i<n;++i) a[i].init();
sort(a,a+n); int Mx=(<<n)-;
for(int i=;i<=Mx;++i){//暴力处理交集
p.xl=;p.yl=;p.xr=h;p.yr=w;
for(int j=,u=i;!p.null()&&u;u>>=,++j)
if(u&) p&=a[j];
ist[i]=p.null()?:p.area();
}
for(int i=;i<=Mx;++i)//暴力处理并集
for(int j=i;j;j=(j-)&i)
uni[i]+=((siz[j]&)?:-)*ist[j];
int nw=,ls=;
ll sum,tot,re,k,ans=Pow(m,h*w-uni[Mx]);
for(int i=;i<n;++i){//分层处理最大值为$a[i].v$的块的方案数
nw|=(<<i);
if(a[i].v==a[i+].v) continue;
sum=uni[nw|ls]-uni[ls];
re=Pow(a[i].v,sum);
for(int u=nw;u;u=(u-)&nw){
tot=uni[u|ls]-uni[ls];
k=Pow(a[i].v-,tot)*Pow(a[i].v,sum-tot)%mod;
if(siz[u]&) re=(re-k+mod)%mod;
else re=(re+k)%mod;
}ans=ans*re%mod; ls|=nw; nw=;
}printf("%lld\n",ans);
}
int main(){
for(int i=;i<=;++i) siz[i]=siz[i>>]+(i&);
scanf("%d",&T);
while(T--) Solve();
return ;
}