HDU-5471 Count the Grid

题目描述

一个矩阵中可以任意填\(m\)个数。给你\(N\)个小矩阵并且告诉你此矩阵中的最大值\(v\)，求有多少种大矩阵满足所给条件。\(（\%1e9+7）\)

Input

包含\(T\)组数据.

第一行有\(h,w,m,n\)四个整数，接下来\(n\)行,每行包含5个整数\(x1，y1，x2，y2，v\).

表示每次选择左上角为\(（x1，y1）\)，右下角为\(（x2，y2）\)的矩形，该矩形的最大值\(v\)。

\(（T=55,1≤h,w,m≤1e4,1≤x1≤x2≤h,1≤y1≤y2≤w,1≤v≤m,1≤n≤10）\)

Output

每个样例输出Case #x: ans

Sample Input

Sample Output

Case #1: 28

Case #2: 76475

容斥神题！！

注意：下文中所提及的矩阵的交集必须仅包含当前的所有矩阵，即不能有其他不在当前状态的矩阵和交集有相交的地方。

我们很容易发现，题目所给出的\(n\)是十分小的，这就意味着我们可以利用状压来求解。

每个小矩阵之间的转移必定是和矩阵的交集或并集相关的，而并集很显然也要求出交集。

那么，我们就利用交集来求解。

一共有\(n\)个矩阵，那么就有\(2^n\)个交集，我们要求出这些交集的面积和最大值。

交集的最大值很好求出，直接\(min\)过去就行了。

而求交集的面积就要利用容斥了，

对于我们当前要求的集合\(s\)，其集合中矩阵相交的面积为\(tot[i]\)。

我们需要去掉其他包含其他矩阵的交集的面积。

我们可以倒着枚举集合\(s\)，同时枚举\(s\)是\(j\)的子集的集合\(j\)。

则集合\(s\)的交集就要减去集合\(j\)的交集。

drep(i,(1<<n)-1,0) {

	tot[i]=B[i].Sum();

	ret(j,i+1,1<<n)if((j|i)==j)tot[i]-=tot[j];

}

合并集合代码：



struct node {//由于要多次合并矩阵，我们可以直接将其封装起来，方便操作

	int xl,yl,xr,yr,val;

	inline void get(void) {

		xl=Read(),yl=Read(),xr=Read(),yr=Read(),val=Read();

	}

	inline int Sum(void) {//求矩阵面积

		return (xl>xr||yl>yr)?0:(xr-xl+1)*(yr-yl+1);

	}

	node operator+(node _)const {//求两的矩阵的相交矩阵

		node Ans;

		Ans.xl=max(xl,_.xl);

		Ans.yl=max(yl,_.yl);

		Ans.yr=min(yr,_.yr);

		Ans.xr=min(xr,_.xr);

		Ans.val=min(val,_.val);

		return Ans;

	}

} B[(1<<10)+5];

int main(){

    B[0]=(node)<%1,1,h,w,m%>;

    ret(i,1,1<<n)if((i^(i&-i)))B[i]=B[i^(i&-i)]+B[i&-i];

}

接下来，我们开始\(dp\).

定义\(dp[i][j]\)为前\(i\)种交集，已经有\(j\)状态的小矩阵满足了条件的方案数。

\(tot[i]\)为第\(i\)个交集的面积，\(val[i]\)为第\(i\)种交集的最大值，\(us[i]\)为\(i\)状态中最大值和交集最大值相同的状态。

对于当前的\(i\)，我们可以对于交集是否取到最大值进行转移，

若取到了最大值，则\(dp[i][j|us[i]]+=dp[i-1][j]*(val[i]^{tot[i]}-(val[i]-1)^{tot[i]})\)。

否则，\(dp[i][j]+=dp[i-1][j]*(val[i]-1)^{tot[i]}\)。

最后答案就是\(dp[(1<<n)-1][(1<<n)-1]\)。

注意：需要利用滚动数组来优化内存

代码如下

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define reg register

#define Raed Read

#define clr(a,b) memset(a,b,sizeof a)

#define Mod(x) (x>=mod)&&(x-=mod)

#define debug(x) cerr<<#x<<" = "<<x<<endl;

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)>(b)?(b):(a))

#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a)

#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a)

#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a)

#define erep(i,G,x) for(int i=(G).Head[x]; i; i=(G).Nxt[i])

#pragma GCC target("avx,avx2,sse4.2")

#pragma GCC optimize(3)

inline int Read(void) {

	int res=0,f=1;

	char c;

	while(c=getchar(),c<48||c>57)if(c=='-')f=0;

	do res=(res<<3)+(res<<1)+(c^48);

	while(c=getchar(),c>=48&&c<=57);

	return f?res:-res;

}

template<class T>inline bool Min(T &a, T const&b) {

	return a>b?a=b,1:0;

}

template<class T>inline bool Max(T &a, T const&b) {

	return a<b?a=b,1:0;

}

const int N=1e5+5,M=7e6+5,mod=1e9+7;

bool MOP1;

int n,dp[2][(1<<10)+5],tot[(1<<10)+5],us[(1<<10)+5];

struct node {

	int xl,yl,xr,yr,val;

	inline void get(void) {

		xl=Read(),yl=Read(),xr=Read(),yr=Read(),val=Read();

	}

	inline int Sum(void) {

		return (xl>xr||yl>yr)?0:(xr-xl+1)*(yr-yl+1);

	}

	node operator+(node _)const {

		node Ans;

		Ans.xl=max(xl,_.xl);

		Ans.yl=max(yl,_.yl);

		Ans.yr=min(yr,_.yr);

		Ans.xr=min(xr,_.xr);

		Ans.val=min(val,_.val);

		return Ans;

	}

} A[15],B[(1<<10)+5];

inline int Pow(int x,int y) {

	int res=1;

	while(y) {

		if(y&1)res=1ll*res*x%mod;

		x=1ll*x*x%mod,y>>=1;

	}

	return res;

}

bool MOP2;

inline void _main() {

	int T=Read(),Case=0;

	while(T--) {

		int h=Read(),w=Read(),m=Read(),n=Read();

		rep(i,1,n)A[i].get(),B[1<<(i-1)]=A[i];

		B[0]=(node)<%1,1,h,w,m%>;

		ret(i,1,1<<n)if((i^(i&-i)))B[i]=B[i^(i&-i)]+B[i&-i];

		drep(i,(1<<n)-1,0) {

			us[i]=0,tot[i]=B[i].Sum();

			ret(j,i+1,1<<n)if((j|i)==j)tot[i]-=tot[j];

			rep(j,1,n)if(A[j].val==B[i].val&&(i&(1<<(j-1))))us[i]|=1<<(j-1);

		}

		int cur=0;

		clr(dp[cur],0),dp[cur][0]=1;

		ret(i,0,1<<n) {

			cur^=1,clr(dp[cur],0);

			int res1=Pow(B[i].val-1,tot[i]);

			int res2=Pow(B[i].val,tot[i]);

			int _cur=!cur;

			ret(j,0,1<<n)if(dp[_cur][j]) {

				dp[cur][j|us[i]]+=1ll*dp[_cur][j]*((res2-res1+mod)%mod)%mod;

				dp[cur][j]+=1ll*dp[_cur][j]*res1%mod;

				Mod(dp[cur][j]),Mod(dp[cur][j|us[i]]);

			}

		}

		printf("Case #%d: %d\n",++Case,dp[cur][(1<<n)-1]);

	}

}

signed main() {

	_main();

	return 0;

}

巴特西