一本通 1783 矩阵填数状压dp 容斥计数

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;

}

巴特西

一本通 1783 矩阵填数状压dp 容斥计数

最新文章

热门文章

巴特西

一本通 1783 矩阵填数 状压dp 容斥 计数

最新文章

热门文章

一本通 1783 矩阵填数状压dp 容斥计数