【算法】离散化+容斥原理
【题意】给定大矩阵，可以每格都可以任意填1~m，给定n个子矩阵，要求满足子矩阵内的最大值为vi，求方案数。
n<=10,h,w<=1w。
【题解】
此题重点之一在于离散化，因为有效坐标很少，离散化后遵循左闭右开计算矩阵点数。
然后对于每个格，能填的最大值是min(m,vi),vi为覆盖到该点的所有小矩阵，就此算出总方案数。
现在多考虑了一些情况，就是每个小矩阵中至少要有一个格子是最大值，不符合的情况需要剔除。
考虑容斥原理，奇加偶减，不过这里是总方案-容斥部分，所以是奇减偶加。
2^n枚举子集，然后对于选中的矩阵为min(vi-1)，未选中的矩阵为min(vi)，其它为m，即强制选中的矩阵不符合条件。
复杂度O(2^n*[n*n^2+n^2*log n])。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=30,M=1000000007; int h,w,m,n,x1[maxn],y1[maxn],x2[maxn],y2[maxn],vx[maxn]; int x[maxn],y[maxn],totx,toty,totv; int mat[maxn][maxn],map[maxn][maxn],ans,s; int pow(int x,int k){ int as=1; while(k){ if(k&1)as=1ll*as*x%M; x=1ll*x*x%M; k>>=1; } return as; } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d%d%d%d",&h,&w,&m,&n); totx=toty=totv=0; x[++totx]=1;x[++totx]=h+1; y[++toty]=1;y[++toty]=w+1; for(int i=1;i<=n;i++){ scanf("%d%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i],&vx[i]); x[++totx]=x1[i];x[++totx]=x2[i]+1; y[++toty]=y1[i];y[++toty]=y2[i]+1; } sort(x+1,x+totx+1);totx=unique(x+1,x+totx+1)-x-1; sort(y+1,y+toty+1);toty=unique(y+1,y+toty+1)-y-1; for(int i=1;i<totx;i++)for(int j=1;j<toty;j++)mat[i][j]=(x[i+1]-x[i])*(y[j+1]-y[j]); for(int i=1;i<=n;i++){ x1[i]=lower_bound(x+1,x+totx+1,x1[i])-x; x2[i]=lower_bound(x+1,x+totx+1,x2[i]+1)-x; y1[i]=lower_bound(y+1,y+toty+1,y1[i])-y; y2[i]=lower_bound(y+1,y+toty+1,y2[i]+1)-y; } ans=0; for(int S=0;S<(1<<n);S++){ int num=0; for(int i=1;i<totx;i++)for(int j=1;j<toty;j++)map[i][j]=m; for(int k=1;k<=n;k++){ int mx=vx[k]; if(S&(1<<(k-1))){mx--;num++;} for(int i=x1[k];i<x2[k];i++)for(int j=y1[k];j<y2[k];j++)map[i][j]=min(map[i][j],mx); } if(num&1)s=-1;else s=1; for(int i=1;i<totx;i++)for(int j=1;j<toty;j++)s=1ll*s*pow(map[i][j],mat[i][j])%M; ans=(ans+s)%M; } printf("%d ",(ans+M)%M); } return 0; }
可以优化一下，统计每个策略时本来是枚举所有点，改为枚举所有权值，因为快速幂取模很慢，所以速度得到了巨大的提升……
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=30,M=1000000007; int h,w,m,n,x1[maxn],y1[maxn],x2[maxn],y2[maxn],vx[maxn]; int x[maxn],y[maxn],v[maxn],totx,toty,totv; int mat[maxn][maxn],map[maxn][maxn],ans,s,c[maxn]; int pow(int x,int k){ int as=1; while(k){ if(k&1)as=1ll*as*x%M; x=1ll*x*x%M; k>>=1; } return as; } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d%d%d%d",&h,&w,&m,&n); totx=toty=totv=0; x[++totx]=1;x[++totx]=h+1; y[++toty]=1;y[++toty]=w+1; v[++totv]=m; for(int i=1;i<=n;i++){ scanf("%d%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i],&vx[i]); x[++totx]=x1[i];x[++totx]=x2[i]+1; y[++toty]=y1[i];y[++toty]=y2[i]+1; v[++totv]=vx[i];v[++totv]=vx[i]-1; } sort(x+1,x+totx+1);totx=unique(x+1,x+totx+1)-x-1; sort(y+1,y+toty+1);toty=unique(y+1,y+toty+1)-y-1; sort(v+1,v+totv+1);totv=unique(v+1,v+totv+1)-v-1; for(int i=1;i<totx;i++)for(int j=1;j<toty;j++)mat[i][j]=(x[i+1]-x[i])*(y[j+1]-y[j]); for(int i=1;i<=n;i++){ x1[i]=lower_bound(x+1,x+totx+1,x1[i])-x; x2[i]=lower_bound(x+1,x+totx+1,x2[i]+1)-x; y1[i]=lower_bound(y+1,y+toty+1,y1[i])-y; y2[i]=lower_bound(y+1,y+toty+1,y2[i]+1)-y; vx[i]=lower_bound(v+1,v+totv+1,vx[i])-v; } ans=0; for(int S=0;S<(1<<n);S++){ int num=0; for(int i=1;i<totx;i++)for(int j=1;j<toty;j++)map[i][j]=totv; for(int k=1;k<=n;k++){ int mx=vx[k]; if(S&(1<<(k-1))){mx--;num++;} for(int i=x1[k];i<x2[k];i++)for(int j=y1[k];j<y2[k];j++)map[i][j]=min(map[i][j],mx); } if(num&1)s=-1;else s=1; for(int i=1;i<=totv;i++)c[i]=0; for(int i=1;i<totx;i++)for(int j=1;j<toty;j++)c[map[i][j]]+=mat[i][j]; for(int i=1;i<=totv;i++)s=1ll*s*pow(v[i],c[i])%M; ans=(ans+s)%M; } printf("%d ",(ans+M)%M); } return 0; }